METODE STEEPEST DESCENT Dosen Pengampu: Rukmono Budi Utomo M.Sc.
Disusun Oleh : Linna Tri Lestari (6A1) 1384202140
Diajukan sebagai tugas Ujian Akhir Semester (UAS) Metode Numerik
UNIVERSITAS MUHAMMADIYAH TANGERANG FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN MATEMATIKA June 5, 2016
1
KATA PENGANTAR Alhamdulillah, segala puji dan syukur kami panjatkan kepada Allah SWT. atas rahmat dan karunia yang telah diberikan-Nya, sehingga penulis dapat menyelesaikan makalah ini dengan baik. Dalam penulisan makalah ini dibuat dalam format latex document untuk memenuhi tugas ujian akhir semester mata kuliah metode numerik semester 6 di Universitas Muhammadiyah Tangerang. Selain itu saya juga berharap makalah ini mampu memberikan kontribusi, memberi gambaran ataupun menjadi referensi kita dalam mengenal dan mempelajari materi yang akan dibahas. Saya menyadari bahwa masih jauh dari kesempurnaan, oleh karena itu kritik dan saran yang membangun sangat saya harapkan demi kesempurnaan di masa yang akan datang. Tangerang, 05 Juni 2016 Linna Tri Lestari
2
1 PENDAHULUAN 1.1 Latar Belakang Metode numerik adalah teknik untuk menyelesaikan permasalahan-permasalahan yang diformulasikan secara metematik dengan cara operasi hitungan (arithmetic). Penggunaan metode numerik dilakukan karena tidak semua permasalahan matematis atau perhitungan matematis dapat diselesaikan dengan mudah. Bahkan dalam prinsip matematik suatu persoalan matematik yang paling pertama dilihat adalah apakah persoalan itu memiliki penyelesaian atau tidak. Jadi, jika suatu persoalan sudah sangat sulit atau tidak mungkin diselesaikan dengan metode matematis (analitik) maka kita dapat menggunakan metode nmerik sebagai alternative penyelesaian persoalan tersebut. Dalam perkuliahan metode numerik di semester 6 lalu kita telah membahas berbagai macam metode numerik mulai dari metode golden ratio, metode bisection,metode fibonacci, metode newton, metode aksial, dichotomus, secant, hooke and jeeves, arah konjugasi, roosenberg. Dalam makalah ini yang akan dibahas adalah metode steepest descent, yang erat kaitannya dengan metode aksial, hooke and jeeves, arah konjugasi serta roosenberg.
1.2 Rumusan Masalah • Menjelaskan pengertian dari metode numerik steepest descent • Menjelaskan algoritma metode steepest descent • Menjelaskan contoh penyelesaian metode steepest descent
1.3 Tujuan dan Manfaat Adapun tujuan dari penulisan makalah ini adalah untuk memenuhi tugas ujian akhir semester mata kuliah metode numerik di semester 6, serta berbagi pengetahuan kepada para pembaca mengenai materi yang akan dibahas yaitu metode steepest descent. Manfaat yang dapat petik dari tujuan tersebut yaitu diharapkan dapat menambah wawasan para pembaca dan khususnya untuk mahasiswa-mahasiswi Universitas Muhammadiyah Tangerang.
3
2 PEMBAHASAN 2.1 Pengertian Metode Steepest Descent Metode steepest descent juga dikenal dengan nama metode gradient. Metode steepest descent merupakan prosedur paling mendasar yang diperkenalkan oleh Cauchy pada tahun 1847. Metode ini adalah metode gradien sederhana yang menggunakan vektor gradien untuk menentukan arah pencarian pada setiap iterasi. Kemudian, dari arah tersebut akan ditentukan besar ukuran langkahnya. Metode Steepest Descent digunakan untuk mencari minimum suatu fungsi, yakni dengan menggunakan nilai negatif dari gradient fungsi disuatu titik. Digunakan nilai negatif dari gradient karena gradien memberikan nilai kenaikan yang semakin besar. Dengan nilai negatif dari gradient maka akan diperoleh nilai penurunan yang semakin besar. Metode Steepest Descent digunakan untuk mencari minimum suatu fungsi, yakni dngan menggunakan nilai negatif dari gradient fungsi disuatu titik. Digunakan nilai negatif dari gradient karena gradien memberikan nilai kenaikan yang semakin besar. Dengan nilai negatif dari gradient maka akan diperoleh nilai penurunan yang semakin besar. Pada beberapa kasus, metode steepest descent ini memiliki kekonvergenan yang lambat menuju solusi optimum karena langkahnya berbentuk zig-zag. Metode ini dapat digunakan untuk optimasi tanpa kendala maupun dengan kendala.
2.2 Algoritma Metode Steepest Descent 1. Diberikan fungsi Z = f (x) untuk mencari nilai (x1 , x2 ), XR2 yang meminimumkan fungsi tersebut 2. Tentukan titik awal x ¯k = (x1 , x2 ), ε atau error yang ditentukan dan ambil k = 0 3. Dihitung gradient dari f (x) pada titik xk ,yaitu ∇f (¯ xk ). 4. Kemudian dihitung ∇f (¯ xk ). Jika ||∇f (¯ xk )|| < ε, iterasi dihentikan dan pilih xk sebagai titik minimum. Jika sebaliknya, lanjutkan ke langkah selanjutnya. 5. Misalkan arah pencarian pada titik x ¯k adalah dk = −∇f (xk ). 6. Dihitung λk = minZ(¯ xk + λk dk ) 7. Derivatifkan Z(¯ xk + λk dk ) dan sama dengankan nol untuk menentukan nilai λk 8. Dihitung x ¯k+1 dimana x ¯k+1 = x ¯k + λk dk 9. Iterasi terhenti ketika ||∇f (¯ xk )|| < Kondisi ∇f (¯ xk ) = 0 kerapkali tidak dapat dengan tetap dipenuhi karena perhitungan secara numerik dari gradient akan jarang tetap sama dengan nol. Dalam kasus demikian maka sebagai kriteria penghentian adalah dengan mengecek norma gradient, yakni jika norma ||∇f (¯ xk )|| dari gradient adalah tidak lebih besar dari suatu toleransi yang diberikan maka iterasi dihentikan sebagai alternatif dapat juga dilakukan dengan menghitung perbedaan nilai mutlak ||f (¯ xk+1 − (¯ xk )|| diantara nilai objektif untuk setiap dua iterasi brturut-turut. Jika perbedaannya tidak lebih besar dari suatu toleransi yang diberikan maka perhitungan diberikan. Agar lebih mudah dalam memahami algoritma metode Stepeest Descent,dibawah ini diberikan diagram alir metode Stepeest Descent. 4
Figure 1: Diagram alir algoritma Steepest Descent
2.3 Contoh Soal 1. Diberikan suatu fungsi f (X) = 6x21 + 2x22 + 2x1 x2 − 12x1 − 2x2 + 6, dengan menggunakan metode steepest descent, tentukan pembuat minimum jika diberikan titik awal (0, 1) dan ε = 0.2 Penyelesaian: ITERASI I • Dari soal diketahui fungsi awal f (X) = 6x21 + 2x22 + 2x1 x2 − 12x1 − 2x2 + 6 dengan titik awal x0 = (0, 1) dan ε = 0.2 • Untuk mencari ∇f (¯ x0 ), terlebih dahulu turunan dari x1 terhadap fungsi f(X) dan turunan x2 terhadap fungsi f(X) yaitu sebagai berikut: ∂F ∂x1 = 12x1 + 2x2 − 12 ∂F ∂x2 = 4x2 + 2x1 − 2 maka : ∇f (¯ x0 ) = ∇f (x1 , x2 ) = ∇f (0, 1) ! ! 12(0) + 2(1) − 12 −10 ∇f (¯ x0 ) = = 4(1) + 2(0) − 2 2 • Kemudian cek apakah ||∇f (¯ x0 )|| < ! ε atau > ε yaitu dengan cara :
−10 q √
2 2 k∇f (x0 )k = k∇f (0, 1)k =
= (−10) + (2) = 104 = 10.2
2 Karena ||∇f (¯ x0 )|| = 10.2 > ε maka memenuhi syarat bahwa iterasi dilanjutkan.
5
• Mencari arah pencarian d0 ! −10 d0 = −∇f (¯ x0 ) = − = 2
10 −2
!
• Mencari nilai λ0 yaitu dengan cara sebagai berikut : λ0 = min Z(¯ x0 + λ0 d0 ) λ0 = min Z((0, 1) + λ0 (10, −2)) λ0 = min Z((0, 1) + (10λ0 , −2λ0 )) λ0 = min Z(10λ0 , −2λ0 + 1) Subtitusikan Z(10λ0 , −2λ0 + 1) ke persamaan awal: Z(10λ0 , −2λ0 +1) = 6(10λ0 )2 +2(−2λ0 +1)2 +2((10λ0 )(−2λ0 +1))−12(10λ0 )−2(−2λ0 +1)+6
Z(10λ0 , −2λ0 + 1) = 600λ20 + 8λ20 − 8λ0 + 2 − 40λ20 + 20λ0 − 120λ0 + 4λ0 − 2 + 6 Z(10λ0 , −2λ0 + 1) = 568λ20 − 104λ0 + 6 Kemudian turunkan fungsi Z diatas dan sama dengankan nol untuk memperoleh λ0 : dZ ⇔ dλ =0 0 ⇔ 1136λ0 − 104 = 0 ⇔ 1136λ0 = 104 104 ⇔ λ0 = 1136 = 0.091549295 ⇔ λ0 ≈ 0.092 • Mencari nilai x ¯1 x ¯1 = x ¯0 + λ0 d0 x ¯1 = (0, 1) + 0.092(10, −2) x ¯1 = (0, 1) + (0.92, −0.184) x ¯1 = (0.92, 0.816) ITERASI II • Dari iterasi 1 diperoleh x ¯1 = (0.92, 0.816) • Mencari ∇f (¯ x1 ): ∇f (¯ x1 ) = ∇f (0.92, 0.816) ! 12(0.92) + 2(0.816) − 12 ∇f (¯ x1 ) = = 4(0.816) + 2(0.92) − 2
11.04 + 1.632 − 12 3.264 + 1.84 − 2
!
=
0.672 3.104
!
• Kemudian cek apakah x1 )||
||∇f (¯ ! < ε atau > ε yaitu dengan cara :
0.672 q √
2 2 k∇f (0.92, 0.816)k =
= (0.672) + (3.104) = 0.451584 + 9.634816 =
3.104 √ 10.0864 = 3.176 Karena ||∇f (¯ x1 )|| = 3.176 > ε maka memenuhi syarat bahwa iterasi dilanjutkan. • Mencari arah pencarian d1 ! 0.672 d1 = −∇f (¯ x1 ) = − = 3.104
−0.672 −3.104
!
• Mencari nilai λ1 yaitu dengan cara sebagai berikut : λ1 = min Z(¯ x1 + λ1 d1 ) λ1 = min Z((0.92, 0.816) + λ1 (−0.672, −3.104)) 6
λ1 = min Z((0.92, 0.816) + (−0.672λ1 , −3.104λ1 )) λ1 = min Z(−0.672λ1 + 0.92, −3.104λ1 + 0.816) Subtitusikan Z(−0.672λ1 + 0.92, −3.104λ1 + 0.816) ke persamaan awal: Z(−0.672λ1 + 0.92, −3.104λ1 + 0.816) = 6(−0.672λ1 + 0.92)2 + 2(−3.104λ1 + 0.816)2 + 2(−0.672λ1 + 0.92)(−3.104λ1 + 0.816)) − 12(−0.672λ1 + 0.92) − 2(−3.104λ1 + 0.816) + 6
= 26.150912λ21 − 10.0864λ1 + 1.239552 Kemudian turunkan fungsi Z diatas dan sama dengankan nol untuk memperoleh λ1 : dZ ⇔ dλ =0 1 ⇔ 52.301824λ1 − 10.0864 = 0 ⇔ 52.301824λ1 = 10.0864 10.0864 ⇔ λ1 = 52.301824 = 0.1928498708 ⇔ λ1 ≈ 0.193 • Mencari nilai x ¯2 x ¯2 = x ¯1 + λ1 d1 x ¯2 = (0.92, 0.816) + 0.193(−0.672, −3.104) x ¯2 = (0.92, 0.816) + (−0.129696, −0.599072)) x ¯2 = (0.790304, 0.216928) x ¯2 ≈ (0.79, 0.217) ITERASI III • Dari iterasi 2 diperoleh x ¯2 = (0.79, 0.217) • Mencari ∇f (¯ x2 ): ∇f (¯ x2 ) = ∇f (0.79, 0.217) ! 12(0.79) + 2(0.217) − 12 = ∇f (¯ x2 ) = 4(0.217) + 2(0.79) − 2
2.48 + 0.434 − 12 0.868 + 1.58 − 2
!
=
−2.086 0.448
!
• Kemudian cek apakah x2 )||! < ε atau > ε yaitu dengan cara :
||∇f (¯
−2.086 q √
2 2 k∇f (0.92, 0.816)k =
= (−2.086) + (0.448) = 4.351396 + 0.200704 =
0.448 √ 4.5521 = 2.136 Karena ||∇f (¯ x2 )|| = 2.136 > ε maka memenuhi syarat bahwa iterasi dilanjutkan. • Mencari arah pencarian d2 ! −2.086 d2 = −∇f (¯ x2 ) = − = 0.448
2.086 −0.448
!
• Mencari nilai λ2 yaitu dengan cara sebagai berikut : λ2 = min Z(¯ x2 + λ2 d2 ) λ2 = min Z((0.79, 0.217) + λ2 (2.086, −0.448)) λ2 = min Z((0.79, 0.217) + (2.086λ2 , −0.448λ2 )) λ2 = min Z(2.086λ2 + 0.79, −0.448λ2 + 0.217) Subtitusikan Z(2.086λ2 + 0.79, −0.448λ2 + 0.217) ke persamaan awal : Z(2.086λ2 + 0.79, −0.448λ2 + 0.217) 7
= 6(2.086λ2 + 0.79)2 + 2(−0.448λ2 + 0.217)2 + 2(2.086λ2 + 0.79)(−0.448λ2 + 0.217)) − 12(2.086λ2 + 0.79) − 2(−0.448λ2 + 0.217) + 6
= 28.37884λ22 − 4.5521λ2 + 0.267638 Kemudian turunkan fungsi Z diatas dan sama dengankan nol untuk memperoleh λ2 dZ =0 ⇔ dλ 2 ⇔ 56.75768λ2 − 4.5521 = 0 ⇔ 56.75768λ2 = 4.5521 4.5521 ⇔ λ2 = 56.75768 = 0.080202362 ⇔ λ2 ≈ 0.08 • Mencari nilai x ¯3 x ¯3 = x ¯2 + λ2 d2 x ¯3 = (0.79, 0.217) + 0.08(2.086, −0.448) x ¯3 = (0.79, 0.217) + (0.16688, −0.03584)) x ¯3 = (0.95688, 0.18116) x ¯3 ≈ (0.96, 0.18) ITERASI IV • Dari iterasi 3 diperoleh x ¯3 = (0.96, 0.18) • Mencari ∇f (¯ x3 ): ∇f (¯ x3 ) = ∇f (0.96, 0.18) ! 12(0.96) + 2(0.18) − 12 = ∇f (¯ x3 ) = 4(0.18) + 2(0.96) − 2
11.52 + 0.36 − 12 0.72 + 1.92 − 2
!
=
−0.12 0.64
!
• Kemudian cek apakah x3 )|| > ε yaitu dengan cara :
||∇f (¯ ! < ε atau q
−0.12 √
k∇f (0.96, 0.18)k = (−0.12)2 + (0.64)2 = 0.0144 + 0.4096 =
=
0.64 √ 0.424 = 0.651 Karena ||∇f (¯ x3 )|| = 0.651 > ε maka memenuhi syarat bahwa iterasi dilanjutkan. • Mencari arah pencarian d3 ! −0.12 d3 = −∇f (¯ x2 ) = − = 0.64
0.12 −0.64
!
• Mencari nilai λ3 yaitu dengan cara sebagai berikut : λ3 = min Z(¯ x3 + λ3 d3 ) λ3 = min Z((0.96, 0.18) + λ3 (0.12, −0.64)) λ3 = min Z((0.96, 0.18) + (0.12λ3 , −0.64λ3 )) λ3 = min Z(0.12λ3 + 0.96, −0.64λ3 + 0.18) Subtitusikan Z(0.12λ3 + 0.96, −0.64λ3 + 0.18) ke persamaan awal : Z(0.12λ3 + 0.96, −0.64λ3 + 0.18) = 6(0.12λ3 + 0.96)2 + 2(−0.64λ3 + 0.18)2 + 2(0.12λ3 + 0.96)(−0.64λ3 + 0.18)) − 12(0.12λ3 + 0.96) − 2(−0.64λ3 + 0.18) + 6
= 0.752λ23 − 0.424λ3 + 0.06 Kemudian turunkan fungsi Z diatas dan sama dengankan nol untuk memperoleh λ3 dZ ⇔ dλ =0 3 8
⇔ 1.504λ3 − 0.424 = 0 ⇔ 1.504λ3 = 0.424 ⇔ λ3 = 0.424 1.504 = 0.28191489 ⇔ λ3 ≈ 0.282 • Mencari nilai x ¯4 x ¯4 = x ¯3 + λ3 d3 x ¯4 = (0.96, 0.18) + 0.282(0.12, −0.64) x ¯4 = (0.96, 0.18) + (0.033, −0.18048)) x ¯4 = (0.99384, 0.00048) x ¯4 ≈ (0.994, 0.0005) ITERASI V • Dari iterasi 4 diperoleh x ¯4 = (0.994, 0.0005) • Mencari ∇f (¯ x4 ): ∇f (¯ x4 ) = ∇f (0.79, 0.217) ! 12(0.994) + 2(0.0005) − 12 ∇f (¯ x4 ) = = 4(0.0005) + 2(0.994) − 2
11.928 + 0.001 − 12 0.002 + 1.988 − 2
!
=
−0.071 −0.01
!
• Kemudian cek apakah ||∇f (¯ x4 )|| ε yaitu dengan cara :
−0.071 q √
2 2 k∇f (0.994, 0.0005)k =
= (−0.071) + (−0.01) = 0.005041 + 0.0001 =
−0.01 √ 0.015041 = 0.123 Karena ||∇f (¯ x4 )|| = 0.123 < ε maka telah memenuhi syarat bahwa iterasi terhenti. TABEL ITERASI Dengan konsep Metode Numerik Steepest Descent maka perhitungan yang diperoleh disajikan dalam tabel dibawah ini: Iterasi I II III IV V
xk (0,1) (0.92, 0.816) (0.79, 0.217) (0.96, 0.18) (0.994, 0.0005)
∇f (xk ) (-10, 2) (0.672, 3.104) (-2.086, 0.448) (-0.12, 0.64) (-0.071, -0.01)
||∇f (xk )|| 10.2 > ε 3.176 > ε 2.136 > ε 0.651 > ε 0.123 < ε
9
dk (10, -2) (-0.672, -3.104) (2.086, -0.448) (0.12, -0.64)
.....
λk 0.092 0.193 0.08 0.282 .....
x¯k (0.92, 0.816) (0.79, 0.217) (0.96, 0.18) (0.994, 0.0005)
.......
Pembuktian dengan Cara Analitik • Dalam soal diberikan fungsi f (X) = 6x21 + 2x22 + 2x1 x2 − 12x1 − 2x2 + 6, kemudian dicari turunan-turunan sebagai berikut: ∂f = 12x1 + 2x2 − 12..............(1) ⇔ ∂x 1 ∂f ⇔ ∂x = 4x2 + 2x1 − 2..............(2) 2 ⇔ ⇔ ⇔
∂2f = ∂x21 2 ∂ f = ∂x22 2 ∂ f ∂x1 ∂x2
12 4 =2
• Dicari nilai δ yaitu : 2
2
2
f δ = ( ∂∂xf2 )( ∂∂xf2 ) − ( ∂x∂1 ∂x )2 = 12(4) − 22 = 48 − 4 = 44 > 0 2 1
2
• Kemudian untuk mencari nilai (x1 , x2 ) menggunakan cara sebagai berikut : Eliminasi Persamaan (1) dan (2) 12x1 + 2x2 − 12 = 0| × 2| → 24x1 + 4x2 − 24 = 0 4x2 + 2x1 − 2 = 0| × 1| → 4x2 + 2x1 − 2 = 0 diperoleh nilai : 22x1 − 22 = 0 x1 = 1 Subtitusi nilai x1 = 1 ke persamaan (2): 4x2 + 2x1 − 2 = 0 4x2 + 2(1) − 2 = 0 4x2 = 0 x2 = 0 • Karena δ > 0 maka terbukti bahwa (x1 , x2 ) = (1, 0) meminimumkan fungsi Z = f (x) tersebut.
10
3 PENUTUP 3.1 Kesimpulan Metode steepest descent merupakan metode numerik untuk menyelesaikan persoalan optimasi dalam mencari nilai nilai (x1 , x2 ) yang meminimumkan fungsi Z=f(X) dengan x ¯R2 (dalam perkuliahan ini dibatasi sampai R2 ). Penyelesaian optimasinya berkaitan dengan metode aksial, hook and jeeves, arah konjugasi serta roosenberg. Hanya saja metode steepest descent ini dalam mencari arah pencariannya berbeda dari pada yang lainnya.
3.2 Saran Setelah membahas materi mengenai metode steepest descent, penulis mengharapkan agar selanjutnya materi ini dapat dikembangkan lebih jauh terutama mengenai penyelesaian optimasinya. Karena belajar mengenai metode ini tidaklah mudah, dibutuhkan pemahaman yang mendalam untuk dapat menyelesaikannnya. Penulis berharap agar makalah ini dapat memberikan manfaat kepada setiap orang yang membacanya. Kritik dan saran yang membangun sangat penulis perlukan demi kesempurnaan di masa yang akan datang.
11
