FUNGSI KONVEKS DAN KONKAF

Bagi himpunan R • Himpunan R konveksjika x., y z= (i-t) x + t y , t [0, 1 ]

x z y

• Sebuah fungsi f(x) konveks pada jika x., y : f((1-t) x + t y) < (1-t)f(x) + tf(y), t [0,1]

• Sebuah fungsi f(x) konkaf pada jika x., y : f((1-t) x + t y) (1-t)f(x) + tf(y), t [0,1]

TEOREMA 1

Jika f(x) konveks pada maka lokaI minimum adalah global minimum,

Jika f(x) konkaf pada maka lokaI maksimum adalah global maksimum.

TEOREMA 2

(fungsi konveks yang dapat diturunkan satu kali) adalah konveks pada jika dan hanya jika:

x

(fungsi konkafyang dapat diturunkan satu kali) adalah konkaf pada jika dan hanya jika:

x

TEOREMA3:

 • (fungsi konveks yang dapat diturunkan dua kali) adalah

fungsi konveks jika dan hanya jika:

• (fungsi konkaf yang dapat diturunkan dua kali) adalah fungsi konkaf jika dan hanya jika:

Contoh:

f(x) = eX dan f(x) = x2 adalah fungsi konveks

f(x) = adalah fungsi konkaf

Bagi himpunan dengan dimensi n: Rn

Rn adalah himpunan konveks jikax, y z = (1-t) x + t y , t [0,1]

di mana x = (x1 ,…,xn)

TEOREMA: • f : R adalah fungsi konveks jika x, y : f(( 1-t) x + t y ) < (1-t)f(x) + t f(y), t [0,1] dan

f(y) > f(x) + (y-x)' f(x) • f : R adalah fungsi konkaf jika x, y : f(( 1-t) x + t y ) ≥ 1-t)f(x) + t f(y), t [0,1] dan

f(y) ≤ f(x) + (y-x)' f(x)

Dimana

Adalah vektor gradien

Matriks Hessian suatu fungsi

𝛻2 𝑓 (𝒙)=[𝜕 𝑓 (𝒙 )𝜕𝑥1

❑❑2

𝜕 𝑓 (𝒙 )𝜕 𝑥1𝑥2

…𝜕 𝑓 (𝒙)𝜕 𝑥1𝑥𝑛

⋮ ⋮ ⋮𝜕 𝑓 (𝒙 )𝜕 𝑥𝑛 𝑥1

𝜕 𝑓 (𝒙 )𝜕 𝑥𝑛 𝑥2

…𝜕 𝑓 (𝒙)𝜕 𝑥𝑛𝑥𝑛

❑]

TEOREMA: • Jika bersifat positif semi definit maka f adalah fungsi

konveks dalam • Jika bersifat positif definit maka f adalah fungsi konveks

ketat dalam

Definisi:• Matriks A berukuran nx n adaiah matriks positif semi

definit jika:

Q(x) = x’Ax > 0 x 0• Bersifat positif definit jika:

Q(x) = x’Ax > 0 x 0

TEOREMA: • Jika bersifat negatif semi definit maka f adalah fungsi

konkaf dalam • Jika bersifat negatif definit maka f adalah fungsi konkaf

ketat dalam

Definisi:• Matriks A berukuran nx n adaiah matriks negatif semi

definit jika:

Q(x) = - x’Ax > 0 x 0• Bersifat nagatif definit jika:

Q(x) = - x’Ax > 0 x 0

Definisi: • Minor utama ke i dari matriks nx n adalah determinan

dari matriks i x i yang diperoleh dari penghapusan n-i baris dan n-i kolom yang bersesuaian dari matriks tersebut

TEOREMA: • Suatu matriks A dikatakan positif semi definit jika seluruh

minor utama dari A bernilai >0 (non negatif) • Suatu matriks A dikatakan positif definit jika seluruh minor

utama dari A bemilai >0 (positif) • Suatu matriks A dikatakan negatif semi definit jika minor

utama ke-i dari A bernilai 0 atau bertanda (-1) i ,i = 1, ... ,n. • Suatu matriks A dikatakan negatif definit jika seluruh

minor utama dari A bertanda (-1) i ,i = 1, ... ,n

Dari teorema sebelumnya berlaku:

• Jika f(x) mempunyai turunan parsial kedua yang kontinyu pada x ,maka f(x) adalah fungsi konveks pada jika seluruh minor utama dari adalah >0 (konveks ketat jika seluruh minor utama dari adalah >0).

• Jika f(x) mempunyai turunan parsial kedua yang kontinyu pada x , maka f(x) adalah fungsi konkaf pada jika seluruh minor utama dari bertanda (-1) i ,i = 1, ... ,n atau sama dengan 0 ( konkaf ketat jika seluruh minor utama dari bertanda (-1) i ,i = 1, ... ,n)