BAB 2 URAIAN TEORITIS

BAB 2

URAIAN TEORITIS

Pada bab ini akan dibahas tentang masalah optimisasi berpembatas persamaan. Sebelum membahas masalah optimisasi berpembatas persamaan maka terlebih dahulu diberikan pengertian dan sifat-sifat ekstrim dari suatu fungsi. 2.1 Titik Ekstrim dari Suatu Fungsi Titik ekstrim dari suatu fungsi adalah titik maksimum atau titik minimum dari fungsi tersebut. Masalah penentuan titik ekstrim dari suatu fungsi mempunyai peranan penting dalam optimisasi. Berikut ini diberikan defenisi titik maksimum dan titik minimum dari suatu fungsi. Defenisi 2.1.1 Misalkan f adalah fungsi riil dengan domain D ⊂ R n . a. Fungsi f dikatakan mempunyai nilai maksimum lokal, jika ada selang buka

(x1 , x2 ) yang

memuat x * sehingga memenuhi f ( x) ≤ f ( x * ), ∀x

pada selang buka tersebut. b. Fungsi f dikatakan mempunyai nilai maksimum global pada titik x * jika f ( x) ≤ f ( x * ), ∀x ∈ D . c. Fungsi f dikatakan mempunyai nilai minimum lokal, jika ada selang buka

(x1 , x2 ) yang

memuat x * sehingga memenuhi f ( x) ≥ f ( x * ), ∀x

pada selang buka tersebut. Fungsi f dikatakan mempunyai nilai minimum global pada titik x * jika f ( x) ≤ f ( x * ), ∀x ∈ D .

Universitas Sumatera Utara

Selanjutnya, misalkan f terdiferensial di x ∈ D ⊂ R n . Jika turunan parsial dari f kontinu di x maka f disebut diferensial secara kontinu di x, dan jika turunan parsial kedua dari f kontinu di x maka f disebut mempunyai turunan parsial kedua yang kontinu di x. Gradien dari f pada x dinotasikan dengan ∇f (x) dan didefenisikan dengan:  δf ( x) δf ( x) δf ( x)   …………………………………………...(2.1) ∇f ( x) =  , ,..., δx 2 δx n   δx1

dan matriks Hessian(H) dari f pada x adalah matriks yang diperoleh dari turunan parsial kedua yang dinotasikan dengan ∇ 2 f ( x). Teorema 2.1.2 (Rao, 1984) Jika f terdefenisi pada selang buka yang memuat x * dan mempunyai minimum lokal di x * dan jika f terdiferensial di x * , maka: ∇f ( x * ) = 0 ……………………………………………………………………(2.2) Bukti:

( )

Andaikan x * adalah titik minimum lokal maka f ' x * ada, ini berarti bahwa limit

( )

kiri dan limit kanan ada dan sama dengan f ' x * .

(

)

(

)

f x* + h − f (x* ) f x* + h − f (x* ) = lim+ = f ' (x * ) lim 0 h h →0 − → h h Jika

h > 0 maka

(

)

f x* + h − f (x* ) ≥ 0 karena h

( )

f x * ≤ f ( x * + h) untuk semua

bilangan-bilangan kecil positif dari h. Untuk h → 0 , maka diperoleh:

( )

f ' x * = lim+ h →0

(

)

f x* + h − f (x* ) ≥ lim+ 0 = 0 h →0 h

Universitas Sumatera Utara

Dan jika h > 0 maka

(

)

f x* + h − f (x* ) ≤0 h

Untuk h → 0 , maka diperoleh:

( )

f ' x * = lim− h →0

(

)

f x* + h − f (x* ) ≤ lim− 0 = 0 h →0 h

( )

( )

( )

Limit kiri = limit kanan = 0, maka f ' x * ada. Karena f ' x * ≥ 0 dan f ' x * ≤ 0 ,

( )

( )

maka dapt disimpulkan bahwa f ' x * = 0 atau ∇f x * = 0. ■ 2.2 Masalah Optimisasi Berpembatas Persamaan Pada masalah optimisasi berikut: Minimumkan f ( x ) Terhadap pembatas: h1 ( x ) = 0  h2 ( x ) = 0   ……………………………(2.3)   hm (x ) = 0

dimana x ∈ D ⊂ R n Pada masalah (2.3) diasumsikan bahwa m ≤ n

dan fungsi-fungsi f dan hi,

(i=1,2,…,m) adalah kontinu dan mempunyai turunan parsial kedua yang kontinu. Dengan mengambil h = (h1,h2,…,hm) maka masalah optimisasi yang terdapat pada persamaan (2.3) tersebut dapat ditulis menjadi: Minimumkan f ( x )

Dengan pembatas:

h( x ) = 0

  ……………………………………….(2.4) x ∈ D ⊂ Rn 

Universitas Sumatera Utara

h( x ) = 0 pada persamaan (2.4) tersebut adalah pembatas fungsi

f ( x ) dan

x ∈ D disebut pembatas himpunan. Suatu titik x ∈ D yang memenuhi seluruh

pembatas fungsi f ( x ) disebut titik fisibel. 2.3 Bidang Singgung Untuk menyelidiki apa syarat agar M menjadi bidang singgung di x * , maka diperlukan konsep titik tetap. Berikut ini diberikan defenisi bidang singgung pada suatu permukaan S.

Defenisi 2.3.1 (Leithold, 1991)

(

)

Jika persamaan suatu permukaan S adalah h x * , y * , z * = 0, maka bidang singgung

( ) vektor normal ∇h(x , y , z ) .

dari S pada titik h x * , y * , z * adalah sebuah bidang melalui titik h dan mempunyai *

*

*

Defenisi 2.3.2 (Luenberger, 1984) Suatu kurva pada permukaan S adalah keluarga titik-titik x(t ) ∈ S dengan parameterisasi kontinu t untuk a ≤ t ≤ b. x' =

Suatu kurva terdiferensial jika

d 2 x(t ) dx(t ) ada dan terdiferensial dua kali jika x" (t ) = ada. Suatu kurva x(t) dt dt 2

disebut melalui titik

x(t ) disebut melalui titik

x * jika

x * = (t ) untuk suatu

t * , a ≤ t * ≤ b.

Defenisi 2.3.3 (Leon, 1999) Jika X = {x1 , x 2 ,..., x n } adalah himpunan vektor, maka X disebut bebas linear jika k1 = k2 = ……= kn = 0 sehingga persamaan vektor k1 x1 + k 2 x 2 + ... + k n x n = 0

Universitas Sumatera Utara

Defenisi 2.3.4 (Luenberger, 1984)

( )

Suatu titik x * yang memenuhi pembatas h x * = 0 disebut titik regular dari

( )

( )

( )

pembatas jika vektor gradien ∇h1 x * , ∇h2 x * ,..., ∇hm x * adalah bebas linier.

Defenisi 2.3.5 (Anton, 1997) Misalkan matriks A = Anxn maka A dikatakan non singular jika ada matriks A-1 disebut invers matriks sedemikian sehingga AA-1 = A-1 A = I.

Defenisi 2.3.6 (Luenberger, 1984) Misalkan A adalah suatu matriks nxn, maka Rank matriks A didefenisikan sebagai banyaknya baris-baris atau kolom-kolom yang bebas linier pada matriks A. misalkan A adalah suatu matriks mxn, jika rank A adalah minimum dari (m,n), maka A dikatakan mempunyai rank penuh.

Teorema 2.3.7 (Luenberger, 1984) Misalkan S adalah permukaan yang didefenisikan oleh h(x) = 0. Persamaan bidang singgung pada titik regular x * dari permukaan S tersebut adalah:

{

( )

}

M = y : ∇h x * y = 0 I

…………………………………………..(2.5)

Bukti: Misalkan T adalah bidang singgung x * maka T ⊂ M , apakah x * titik reguler atau tidak. Untuk suatu kurva x(t ) yang melalui x * pada t = t * yang mempunyai turunan

( )

( )( )

x' t * sehingga ∇h x * x t * ≠ 0 tidak akan terletak pada S. Untuk membuktikan M ⊂ T harus ditunjukkan bahwa jika y ∈ M maka terdapat suatu kurva pada S

Universitas Sumatera Utara

yang melalui x * dengan turunan y. Untuk membangun kurva yang demikian ditinjau persamaan berikut:

(

( )

)

h x * + ty + ∇h x * u (t ) = 0 …………………………………...(2.6) T

Pada persamaan (2.6) untuk t tetap, dianggap u (t ) ∈ R m tidak diketahui dengan parameterisasi kontinu dari t. Pada t = 0 terdapat solusi u(0) = 0. Matriks Jacobian dari sistem tersebut terhadap u pada t = 0 adalah matriks m x m, yaitu:

( ) ( )

∇h x * ∇h x *

T

……………………………………………….(2.7)

( )

Matriks pada (2.7) adalah non singuler karena ∇h x *

adalah rank penuh jika

x * adalah suatu titik tetap, maka untuk suatu solusi terdiferensial secara kontinu

( )

u(t) di daerah − a ≤ t ≤ a kurva x(t ) = x * + ty + ∇h x * u (t ) ada pada S. Dengan T

pendiferensialan (2.12) pada t = 0 diperoleh:

0=

d d  h( x(t )) = h( x * + ty + ∇h( x * )u (t )) dt  t =0 dt 0 = ∇h( x * ) y + ∇h( x * )∇h( x * ) T u ' (0)

Karena y terdefenisi maka diperoleh ∇h( x * ) y = 0 dan karena ∇h( x * )∇h( x * ) T adalah non singular maka dapat disimpulkan bahwa u ' (0) = 0 , sehingga diperoleh: x' (0) = y + ∇h( x * ) T u ' (0) = y Hal ini menunjukkan bahwa kurva yang dibangun mempunyai turunan x * pada yaitu y. ■

2.4

Syarat Orde Satu dan Dua Penurunan syarat perlu agar suatu titik menjadi titik minimum terhadap

pembatas persamaan dapat dinyatakan dalam bidang singgung. Untuk itu akan dijelaskan dengan lemma berikut.

Universitas Sumatera Utara

Lemma 2.4.1 (Luenberger,1984) Misalkan x * adalah titik regular dari pembatas h( x ) = 0 dan titik ekstrim lokal terhadap pembatas tersebut, maka ∀y ∈ R n memenuhi:

( )

∇h x * y = 0 ………………………………………….(2.8)

( )

∇f x * y = 0 ………..…..…………………………….(2.9) Bukti: Misalkan y adalah suatu vektor dalam bidang singgung di x * dan x(t ) adalah kurva pada permukaan terbatas yang melalui x * dengan turunan y pada x * yaitu x(0) = x * , x(0 ) = y dan h( x(t )) = 0 untuk ˗ ɑ ≤ t ≤ ɑ untuk suatu ɑ > 0. Karena x * adalah titik regular, bidang singgung identik dengan himpunan y

( )

yang memenuhi ∇h x * y = 0 dan karena x * adalah titik ekstrim lokal berpembatas dari ƒ maka diperoleh:

d f ( x(t )) dt df dx dx dt

]t =0 = 0

] t =0 = 0

( )

atau ekivalen dengan ∇f x * y = 0 .■

( )

Lemma di atas mengatakan bahwa ∇f x *

adalah ortogonal terhadap bidang

singgung.

Defenisi 2.4.2 (Anton, 1997) Bentuk kuadrat x T Ax disebut definit positif jika x T Ax > 0 untuk semua x ≠ 0 dan bentuk kuadrat x T Ax disebut semi definit positif jika x T Ax ≥ 0.

Universitas Sumatera Utara

Teorema berikut menjelaskan syarat perlu orde dua. Untuk selanjutnya diasumsi ƒ dan h adalah fungsi yang kontinu hingga turunannya yang kedua jelas.

Teorema 2.4.3 (Luenberger, 1984) Misalkan bahwa x’adalah titik minimum lokal dari ƒ terhadap pembatas

h( x ) = 0 dan x * adalah titik reguler dari pembatas tersebut, maka terdapat λ ∈ R m sehingga:

( )

( )

∇f x * + λT ∇h x * = 0 …………………….………………(2.10)

{

( )

}

Jika M = y : ∇h x * y = 0 maka matriks:

( )

L( x * ) = ∇ 2 f x * + λT ∇ 2 h( x ) ……….………………….......(2.11)

( )

adalah semidefinit positif pada M, yaitu : y T L x y ≥ 0, ∀y ∈ M *

Bukti : Karena x(0) = x * adalah minimum lokal dari ƒ, maka berlaku:

d2 f ( x(t ))]t =0 ≥ 0……………………………………………(2.12) dt 2 d dx d f ( x(t )) = f ( x(t )) = ∇f ( x(t ))x' (t ) dx dt dt

d2 d f ( x(t )) = [∇f ( x(t ))x' (t )] 2 dt dt =

d [∇f (x(t ))]x' (t ) + ∇f (x(t )) d x' (t ) dt dt

d d  =  ∇f ( x(t )) x(t ) x' (t ) + ∇f ( x(t ))x" (t ) dt  dx 

Universitas Sumatera Utara

[

]

= ∇ 2 f ( x(t ))x' (t ) x' (t ) + ∇f ( x(t ))x" (t ) = x' (t ) ∇ 2 f ( x(t ))x(t ) + ∇f ( x(t ))x" (t ) T

sehingga:  d2 T f ( x(t )) ≥ x' (0 ) ∇ 2 f ( x(0 ))x' (0 ) + ∇f ( x(0 ))x" (0 ) 2 dt  t =0

≥ x' (0 ) ∇ 2 f (x * )x' (0 ) + ∇f ( x(0 ))x" (0 ) ………………(2.13) T

 d2 T λ h(x(t ))  ≥ 0 ,akan diperoleh dengan cara di atas, yaitu: 2 dt  t =0

[

]

 d2 T T λ h(x(t ))  ≥ x' (t ) λT ∇ 2 h(x(t ))x' (t ) + λT ∇h(x(t ))x(t ) 2 dt  t =0

[

]

maka diperoleh:  d2 T λ h(x(t ))  ≥ x' (0 )T λT ∇ 2 h(x(0 ))x' (0) + λT ∇h(x(0))x(0) 2 dt  t =0

[

]

≥ x' (0 ) λT ∇ 2 h(x * )x' (0 ) + λT ∇h(x * )x(0 ) ……………..(2.14) T

( )

( )

x' (0 ) λT ∇ 2 h x * x' (0 ) + λT ∇h x * x' (0 ) ≥ 0 T

Dengan menambahkan persamaan (2.14) ke persamaan (2.13) maka diperoleh:

[ ( )

( )]

[ ( )

( )]

x' (0 ) ∇ 2 h x * x' (0 ) + λT ∇h x * x' (0 ) + ∇f x * + λT ∇h x * x' (0 ) ≥ 0 T

x' (0 ) L( x * ) x' (0 ) + 0 ≥ 0 T

atau y T L( x * ) y ≥ 0 . ■

Universitas Sumatera Utara

Teorema berikut menjelaskan syarat cukup. Untuk selanjutnya diasumsi f dan h adalah fungsi yang kontinu hingga turunannya yang kedua.

Teorema 2.4.3 (Luenberger, 1984) Misalkan terdapat suatu titik x * yang memenuhi h( x ) = 0 dan λ ∈ R m sehingga:

( )

( )

∇f x * + λT ∇h x * = 0 ……………………………………………..(2.15)

( )

( )

( )

Misalkan juga bahwa matriks L x * = ∇ 2 f x * + λT ∇ 2 h x * adalah definit positif

{

( )

}

( )

pada M = y : ∇h x * y = 0 ∀y ∈ M ; y ≠ 0 sehingga memenuhi y T L x * y > 0 , dan

x * adalah minimum lokal dari y terhadap pembatas h( x ) = 0 . Bukti: Karena x(0 ) = x * adalah minimum lokal dari f dan x’ (0 ) = y dengan y ≠ 0 maka berlaku:

d2 f ( x(t )) dt 2

]t =0 > 0 …………………………………………..(2.16)

d2 d dx f ( x(t )) = f ( x(t )) = ∇f ( x(t ))x' (t ) 2 dx dt dt d2 d f ( x(t )) = [∇f ( x(t ))x' (t )] 2 dt dt =

d [∇f (x(t ))]x(t ) + ∇f (x(t )) d x' (t ) dt dt

d d  =  ∇f ( x(t )) x(t ) x' (t ) + ∇f ( x(t ))x" (t ) dt  dx 

[

]

= ∇ 2 f ( x(t ))x' (t ) x' (t ) + ∇f ( x(t ))x" (t ) = x' (t ) ∇ 2 f ( x(t ))x' (t ) + ∇f ( x(t ))x" (t ) T

Universitas Sumatera Utara

sehingga diperoleh:  d2 T f ( x(t )) > x' (0 ) ∇ 2 f ( x(0 ))x' (0 ) + ∇f ( x(0 ))x" (0 ) 2 dt  t =0 > x' (0 ) ∇ 2 f ( x")x' (0 ) + ∇f ( x(0 ))x" (0 ) T

Untuk

[

]

d2 T λ h(x(t )) t =0 > 0 , akan diperoleh dengan cara di atas, yaitu: dt 2  d2 T λ h( x(t ))  > x' (t )T λT ∇ 2 h(x(t ))x' (t ) + λT ∇h( x(t ))x' (t ) 2 dt  t =0

[

]

Maka diperoleh:

> x' (0 ) λT ∇ 2 h(x * )x' (0 ) + λT ∇h(x * )x' (0 ) T

( )

( )

x' (0 ) λT ∇ 2 h x * x' (0 ) + λT ∇h x * x' (0 ) > 0 T

Dengan menambahkan persamaan (2.18) ke persamaan (2.17) maka diperoleh:

[

( )]

[ ( )

( )]

x' (0 ) ∇ 2 f ( x") + λT ∇ 2 h x * x' (0 ) + ∇f x * + λT ∇h x * x(0 ) ≥ 0 T

( )

( )

( )

( )

( )

Karena L x * = ∇ 2 f x * + λT ∇ 2 h x * dan dari (2.15) yaitu ∇f x * + λT ∇h x * = 0 Maka diperoleh:

( )

x' (0 ) L x * x' (0 ) + 0 > 0 T

Atau

( )

y T L x * y > 0 .■

Universitas Sumatera Utara

2.5 Metode Pengali Lagrange Salah satu metode yang sering digunakan untuk menyelesaikan masalah optimisasi berpembatas persamaan adalah metode pengali Lagrange. Untuk menyelesaikan masalah optimisasi pada persamaan (2.4) didefenisikan suatu fungsi Lagrange

sebagai berikut: ...........................................................(2.19) dan vektor riil tak nol

pada persamaan (2.19) disebut pengali

Lagrange. Jika

adalah titik ekstrim dari

, maka menurut teorema 2.1.2

diperoleh: ..................................................(2.20) dan ....................................................................................(2.21) Dengan memperhatikan persamaan (2.10) dan (2.21) maka dapat disimpulkan bahwa masalah optimisasi pada persamaan (2.4) dapat diselesaikan melalui titik ekstrim dari fungsi Lagrange

pada persamaan (2.19).

Dari persamaan (2.3) dimana

,

, dan karena

adalah suatu vektor maka i = 1 maka persamaan (2.19) dapat juga ditulis dengan

atau

.

Universitas Sumatera Utara