metode steepest descent

Nughthoh Arfawi Kurdhi, M.Sc Department of Mathematics FMIPA UNS

METODE STEEPEST DESCENT

Lisa Apriana Dewi [M0108055], Frety Kurnita Sari [M0110029],dan Steffi Niaretho S. [M0110074]

1. PendahuluanOptimasi untuk fungsi lebih dari satu variabel dapat dilakukan dengan menggunakanturunan, yaitu syarat cukup dan syarat perlu:( ) = dan .Sering dihadapi permasalahan yang gagal memenuhi syarat tersebut tetapi fungsi f(x)masih mempunyai titik optimum. Untuk mengatasi masalah tersebut digunakan uncons-trained optimization technique. Metode ini dibagi menjadi dua, yaitu metode PenyelidikanLangsung (Direct Search Methods) dan Metode Gradien (Gradient Methods).

Metode Penyelidikan Langsung dapat digunakan tanpa memerlukan informasi turunan,tetapi metode ini kurang efisien apabila dibandingkan dengan Metode Gradien. MetodeGradien (Metode Descent) merupakan metode yang memerlukan informasi turunan-turunandalam bentuk vektor vektor Gradien Jacobian. Dalam metode ini juga memerlukaninformasi turuna kedua dalam bentuk matrik Hess (Hessian matrix).

2. PembahasanUntuk menetukan arah gerakan, metode ini menggunakan vektor gradien Jacobian. Metodeini merupakan dasar metode first-order yang memerlukan turunan tingkat pertama. Ambil vektor unit u dengan ‖ ‖ =1. Maka . ∇ ( ) = ‖ ‖. ‖∇ ( )‖. cos dengan adalah sudut antara u dan ∇ ( ). Minimum dicapai dengan cos = −1 (atau = ),

Sehingga = ∇ ( )‖∇ ( )‖ (1)u ∇ ( )

Pada metode steepest descent, sebagai direction (arah) gerakan adalah seperti pada (1) de-ngan tidak memperhatikan skalar (norm dari ∇ ( )), jadi= −∇ ( ) (2)(arah yang diambil adalah negatif dari vektor gradien).

Secara umum, metode ini dimulai dari vektor awal dan secara iteratif bergerak menujuke arah optimum (minimum) menurut aturan := + = − ∇ ( ) (3)dimana adalah panjang langkah optimum sepanjang arah .

AlgoritmaInput : f ∶ R → R, f konveks,∇f vektor asal x ∈ R , toleransi α, k = 0.Step 1 : (line search)

Cari titik minimum fungsi satu variabelg (λ) = f (x − λ∇f (x )), misal minimum adalahStep 2: Set : =x − λ ∇f(x ).

Jika ‖∇f (x )‖ < : STOP , ∗ = , jika tidak set k : = k + 1, ulangi step 1 dan 2.

Gambar 1 berikut memperlihatkan minimisasi dengan menggunakan metode steepestdescent untuk fungsi dua variabel dengan contour-contour elliptik.


Titik awal1

2

34 5

X2

X1

XMin

Gambar 1

Contoh Kasus1. Diketahui: A = 1 11 2 , B = −1−1 , C = 0, = akan dicari minimum dari fungsi kuadra-

tik f(x) yang diperoleh dari matriks A, B, x dan konstanta c diatas, dengan toleransi α = 0,01dan dimulai dadri titik awal = 00 .

Penyelesaian:Fungsi f(x) yang dimaksud adalah

f( , ) = + + = + + − −Gradien dari f∇ = + = // = + − 1+ 2 − 1

Gambar 2. Grafik fungsi f( , ) = + + − −


Gambar 3. Gambar contour-contour dari fungsi f( , ) = + + − −Iterasi 1 : k = 0∇(0) = −1−1 , = −∇ ( ) = 11Untuk menentukan , ditentukan panjang langkah dari meminimumkan( ) = ( + ) = ( , ) = − 2( ) = 5 − 2, " ( ) = 5 > 0didapat = 0,4Jadi = + = 0,40,4∇ ( ) = −0,20,2 , ‖∇ ( )‖ = 0,283 >Jadi bukan titik minimum.

Iterasi 2 : k = 1= −∇ ( ) = 0,2−0,2( ) = ( + ) = (0,4 + 0.2 ; 0,4 − 0,2 )= 0,02 − 0,08 − 0,4( ) = 0,04 − 0,08, "( ) = 0,04 > 0diperoleh = 2= + = 0,80∇ ( ) = −0,2−0,2 , ‖∇ ( )‖ = 0,283 >Jadi bukan titik minimum.

Iterasi 3 : k = 2= −∇ ( ) = 0,20,2( ) = ( + ) = (0,8 + 0,2 ; 0,2 )= 0,1 − 0,08 − 0,48( ) = 0,2 − 0,08, " ( ) = 0,2 > 0diperoleh = 0,4= + = 0,880,08∇ ( ) = −0,040,04 , ‖∇ ( )‖ = 0,057 >Jadi bukan titik minimum.

Iterasi 4 : k = 3= −∇ ( ) = 0,04−0,04( ) = ( + ) = (0,88 + 0,04 ; 0,08 − 0,04 )= 0,0008 − 0,0032 − 0,416( ) = 0,0016 − 0,0032, " ( ) = 0,0018 > 0


diperoleh = 2= + = 0,960∇ ( ) = −0,04−0,04 , ‖∇ ( )‖ = 0,057 >Jadi bukan titik minimum.

Iterasi 5 : k = 4= −∇ ( ) = 0,040,04( ) = ( + ) = (0,96 + 0,04 ; 0,04 )= 0,0024 − 0,0032 − 0,4976( ) = 0,0048 − 0,0032, " ( ) = 0,0048 > 0diperoleh = 0.67= + = 0,990,27∇ ( ) = 0,260,53 , ‖∇ ( )‖ = 0,590 >Jadi bukan titik minimum.

Iterasi 6 : k = 5= −∇ ( ) = −0,26−0,53( ) = ( + ) = (0,96 − 0,26 ; 0,27 − 0,53 )= 0,4525 − 0,3485 − 0,42975( ) = 0,4525 − 0,3485 , " ( ) = 0,4525 > 0diperoleh = 0.67= + = 0,890,07∇ ( ) = −0,040,03 , ‖∇ ( )‖ = 0,05 >Jadi bukan titik minimum.

Iterasi 7 : k = 6= −∇ ( ) = 0,04−0,03( ) = ( + ) = (0,89 + 0,04 ; 0,07 − 0,03 )= 0,0005 − 0,0025 − 0,49675( ) = 0,0005 − 0,0025, " ( ) = 0,0005 > 0diperoleh = 2,5= + = 0,99−0,005∇ ( ) = −0,0050 , ‖∇ ( )‖ = 0,005 <STOP. Jadi merupakan titik minimum.

Tabel 1. Iterasi Kasus 1

Iterasi k ( ) ( ) ‖ ( )‖1 0 00 −1−1 11 0,4 0,40,4 −0,20,2 0,2832 1 0,40,4 −0,20,2 0,2−0,2 2 0,80 −0,2−0,2 0,2833 2 0,80 −0,2−0,2 0,20,2 0,4 0,880,08 −0,040,04 0,0574 3 0,880,08 −0,040,04 0,04−0,04 2 0,960 −0,04−0,04 0,0575 4 0,960 −0,04−0,04 0,040,04 0,67 0,990,27 0,260,53 0,5906 5 0,990,27 0,260,53 −0,26−0,53 0,67 0,890,07 −0,040,03 0,05

7 6 0,890,07 −0,040,03 0,04−0,03 2,5 0,99−0,005 −0,0050 0,005


2. Fungsi: f (x , x ) = 2x + x + 2x x + x − x ,d engan = 0.05 dan dari titik awal = 00 .Penyelesaian:

Gambar 4. Gambar dari fungsi f (x , x ) = 2x + x + 2x x + x − x

Gambar 5. Gambar contour-contour fungsi f (x , x ) = 2x + x + 2x x + x − xIterasi 1 : k = 0∇f(x ) = 1−1 ; u = −∇f(x ) = −11g (λ) = f(x + λu ) = f 00 + λ −11 = f(−λ, λ)f(−λ, λ) = 2λ + λ + 2(−λ)λ + (−λ) − λ= 2λ + λ − 2λ − λ − λ= λ − 2λg (λ) = 2λ − 2g (λ) = 02λ − 2 = 0λ = 2/2λ = 1g (λ) = 2 > 0x = + λ u = 00 + 1 −11 = −11∇f(x ) = −4 + 2 + 12 − 2 − 1 = −1−1‖∇f(x )‖ = (−1) + (−1) = √1 + 1 = √2 =1.4142 > = 0.05

Jadi, x bukan titik minimum.

Iterasi 2 : k = 1∇f(x ) = −1−1 ; u = −∇f(x ) = 11g (λ) = f(x + λu ) = f −11 + λ 11 = f(−1 + λ ; 1 + λ)f(−1 + λ ; 1 + λ)


=2(−1 + λ) + (1 + λ) + 2(−1 + λ)(1 + λ) + (−1 + λ) − (1 + λ)= 2(1 − 2λ + λ ) + (1 + 2λ + λ ) + 2(−1 + λ ) − 1 + λ − 1 − λ= 2 − 4λ + 2λ + 1 + 2λ + λ − 2 + 2λ − 2=5λ − 2λ − 1g (λ) = 10λ − 2g (λ) = 010λ − 2 = 0λ = 2/10λ = 0.2g (λ) = 10 > 0x = + λ u = −11 + 0.2 11 = −0.81.2∇f(x ) = 4(−0.8) + 2(1.2) + 12(1.2) + 2(−0.8) − 1 = 0.2−0.2‖∇f(x )‖ = (0.2) + (−0.2) = √0.04 + 0.04 = √0.08 =0.2828 >

Jadi, x bukan titik minimum.

Iterasi 3 : k = 2∇f(x ) = 0.2−0.2 ; u = −∇f(x ) = −0.20.2g (λ) = f(x + λu ) = f −0.81.2 + λ −0.20.2 = f(−0.8 − 0.2λ ; 1.2 + 0.2λ)f(−0.8 − 0.2λ ; 1.2 + 0.2λ)=0.04λ − 0.08λ − 1.2g (λ) = 0.08λ − 0.08g (λ) = 00.08λ − 0.08 = 0λ = 0.08/0.08λ = 1g (λ) = 0.08 > 0x = + λ u = −0.81.2 + 1 −0.20.2 = −11.4∇f(x ) = 4(−1) + 2(1.4) + 12(1.4) + 2(−1) − 1 = −0.2−0.2‖∇f(x )‖ = (−0.2) + (−0.2) = √0.04 + 0.04 = √0.08 =0.2828 >Jadi, x bukan titik minimum.

Iterasi 4 : k = 3∇f(x ) = −0.2−0.2 ; u = −∇f(x ) = 0.20.2g (λ) = f(x + λu ) = f −11.4 + λ 0.20.2 = f(−1 + 0.2λ ; 1.4 + 0.2λ)f(−1 + 0.2λ ; 1.4 + 0.2λ) = 0.2λ − 0.08λ − 1.24g (λ) = 0.4λ − 0.08g (λ) = 00.4λ − 0.08 = 0λ = 0.08/0.4λ = 0.2g (λ) = 0.8 > 0x = + λ u = −11.4 + 0.2 0.20.2 = −0.961.44∇f(x ) = 4(−0.96) + 2(1.44) + 12(1.44) + 2(−0.96) − 1 = 0.04−0.04‖∇f(x )‖ = (0.04) + (−0.04) = √0.0016 + 0.0016 = √0.0032= 0.05657 >Jadi, x bukan titik minimum.

Iterasi 5 : k = 4∇f(x ) = 0.04−0.04 ; u = −∇f(x ) = −0.040.04g (λ) = f(x + λu ) = f −0.961.44 + λ −0.040.04 = f(−0.96 − 0.04λ ; 1.44 + 0.04λ)


f(−0.96 − 0.04λ ; 1.44 + 0.04λ) = 0.0016λ − 0.0032λ − 1.248.g (λ) = 0.0032λ − 0.0032g (λ) = 00.0032λ − 0.0032 = 0λ = 0.0032/0.0032λ = 1g (λ) = 0.0032 > 0x = + λ u = −0.961.44 + 1 −0.040.04 = −11.48∇f(x ) = 4(−1) + 2(1.48) + 12(1.48) + 2(−1) − 1 = −0.04−0.04‖∇f(x )‖ = (−0.04) + (−0.04) = √0.0016 + 0.0016 = √0.0032= 0.05657 >Jadi, x bukan titik minimum.

Iterasi 6 : k = 5∇f(x ) = −0.04−0.04 ; u = −∇f(x ) = 0.040.04g (λ) = f(x + λu ) = f −11.48 + λ 0.040.04 = f(−1 + 0.04λ ; 1.48 + 0.04λ)f(−1 + 0.04λ ; 1.48 + 0.04λ)=0.008λ − 0.0032λ − 1.2496g (λ) = 0.016λ − 0.0032g (λ) = 00.016λ − 0.0032 = 0λ = 0.0032/0.016λ = 0.2g (λ) = 0.016 > 0x = + λ u = −11.48 + 0.2 0.040.04 = −0.9921.488∇f(x ) = 4(−0.992) + 2(1.488) + 12(1.488) + 2(−0.992) − 1 = 0.008−0.008‖∇f(x )‖ = (0.008) + (−0.008) = √0.000064 + 0.000064 = √0.000128= 0.0113 <Jadi, x titik minimum.

Tabel 2. Iterasi Kasus 2

Iterasi k ( ) ( ) ‖ ( )‖1 0 00 1−1 −11 1 −11 −1−1 1.4142

2 1 −11 −1−1 11 0,2 −0.81.2 0.2−0.2 0.2828

3 2 −0.81.2 0.2−0.2 −0.20.2 1 −11.4 −0.2−0.2 0.2828

4 3 −11.4 −0.2−0.2 0.20.2 0.2 −0.961.44 0.04−0.04 0.05657

5 4 −0.961.44 0.04−0.04 0.04−0.04 1 −11.48 −0.04−0.04 0.05657

6 5 −11.48 −0.04−0.04 0.040.04 0.2 −0.9921.488 0.008−0.008 0.0113


Pertanyaan:1. Nining: Apakah turunan kedua dari fungsi lebih dari 0 bisa menjamin kalau

merupakan titik minimum?Jawab: Jika turunan kedua dari fungsi bernilai lebih dari 0,maka bisa menjaminkalau merupakan titik minimum. Jika nilai turunan keduanya kurang dari 0, makamerupakan titik maksimum.

2. Antin : Bisakah metode ini digunakan untuk menyelesaikan fungsi dengan n variabel?Bagaimana penjelasan dari gambar halaman 48?Jawab: Metode ini dapat digunakan untuk fungsi dengan n variabel. Apabila fungsitersebut merupakan fungsi konveks. Maka dapat dselesaikan dengan metode ini.Gambar pada halaman 48 dengan menggunakan contour-contour. Contour adalahbayangan fungsi yang di plot pada bidang .

3. Rani: Apa perbedaan metode ini dengan Metode Univariat?Jawab: Metode ini akan menghasilkan nilai pendekatan dan menggunakan nilai ,sedangkan metode univariat mengahasilkan nilai eksak dan menggunakan nilai .

4. Indri: Bagaimana penentuan nilai pada metode ini?Jawab: Nilai biasanya ditentukan sendiri. Semakin kecil nilai , semakin dekat pulanilai pendekatan yang diperoleh. Kendalanya, semakin kecil nilai , maka semakinbanyak pula perhitungan iterasi yang harus dilakukan untuk mendapatkan nilaiminimum.

metode steepest descent

Documents