Conjugate Gradient Methods [PDF]

Citation preview

Metode Gradien Konjugasi Pendahuluan Kami sekarang melihat pengoptimalan dalam n-dimensi; ruang desain. Tujuannya adalah untuk meminimalkan 𝐹(𝑥), di mana komponen 𝑥 adalah variabel desain 𝑛 independen. Salah satu cara untuk mengatasi masalah adalah dengan menggunakan suksesi minimum satu dimensi untuk mendekati titik optimal. Strategi dasarnya adalah  







Pilih satu titik 𝑥0 di ruang desain. Loop dengan 𝑖 = 1,2,3, . .. Pilih vektor 𝑣𝑖 Minimalkan 𝐹(𝑥) sepanjang garis melalui 𝑥𝑖−1 ke arah 𝑣𝑖 . Biarkan titik minimum menjadi 𝑥𝑖 . Jika |𝑥𝑖 − 𝑥𝑖−1 | keluar dari loop Akhiri loop



Minimalisasi sepanjang garis dapat dicapai dengan algoritma optimasi satu dimensi (seperti pencarian bagian emas). Satu-satunya pertanyaan yang dibiarkan terbuka adalah bagaimana memilih vektor 𝑣𝑖 . Arah KonjugatType equation here. Perhatikan fungsi kuadrat 1 𝐹(𝑥) = 𝑐 − ∑ 𝑏𝑖 𝑥𝑖 + ∑ ∑ 𝐴𝑖𝑗 𝑥𝑖 𝑥𝑗 2 𝑖



𝑖



𝑗



1 = 𝑐 − 𝑏 𝑇 𝑥 + 𝑥 𝑇 𝐴𝑥 2 Diferensiasi sehubungan dengan hasil xi 𝜕𝐹 = −𝑏𝑖 + ∑ 𝐴𝑖𝑗 𝑥𝑗 𝜕𝑥𝑖 𝑗



Yang dapat ditulis dalam notasi vektor sebagai ∇𝐹 = −𝑏 + 𝐴𝑥 Dimana ∇ adalah gradien 𝐹. Sekarang perhatikan perubahan gradien ketika kita bergerak dari titik 𝑥0 ke arah vektor 𝑢. Gerakan berlangsung sepanjang garis 𝑥 = 𝑥0 + 𝑠𝑢 Di mana jarak dipindahkan. Substitusi menjadi Persamaan. (10.6) menghasilkan persamaan untuk gradien sepanjang 𝑢: ∇F|x0+𝑠𝑢 = −𝑏 + 𝐴(𝑥0 + 𝑠𝑢) = ∇F|x0 + 𝑠 𝐴𝑢



Perhatikan bahwa perubahan gradien 𝑠 adalah 𝐴𝑢. jika perubahan ini tegak lurus terhadap vektor 𝑣; yaitu, jika 𝑣 𝑇 𝐴𝑢 = 0



arah dari 𝑢 dan 𝑣 dikatakan saling konjungtif (noninterfering). Implikasinya adalah bahwa begitu kita telah meminimalkan 𝐹(𝑥) ke arah 𝑣, kita dapat bergerak sepanjang 𝑢 tanpa merusak minimisasi sebelumnya. Untuk fungsi kuadrat dari n variabel independen adalah mungkin untuk membangun arah yang saling konjungtif. Oleh karena itu, perlu tepat n garis minimisasi sepanjang arah ini untuk mencapai titik minimum. Jika 𝐹(𝑥) bukan fungsi kuadrat, Persamaan (10.5) dapat diperlakukan sebagai pendekatan lokal dari fungsi merit, diperoleh dengan memotong ekspansi taylor seri 𝐹(𝑥) sekitar 𝑥0 (lihat lampiran A1) 1 𝐹(𝑥) = 𝐹(𝑥0 ) + ∇F(x0 )(𝑥 − 𝑥0 ) + (𝑥 − 𝑥0 )𝑇 𝐻(𝑥0 )(𝑥 − 𝑥0 ) 2 Sekarang arah konjugasi berdasarkan bentuk kuadrat hanya perkiraan, berlaku di sekitar dekat 𝑥0 . Akibatnya, diperlukan beberapa siklus minimisasi garis 𝑛 untuk mencapai titik optimal. Berbagai metode gradien konjugat menggunakan teknik yang berbeda untuk membangun arah konjugasi. Metode orde-nol hanya bekerja dengan 𝐹(𝑥) saja, sedangkan putasional lebih efisien, tentu saja, tetapi masukan 𝐹(𝑥) and ∇F (jika tersedia sama sekali) bisa sangat monoton.



Metode Powell Metode Powells adalah metode zero-order, membutuhkan evaluasi 𝐹(𝑥) saja. jika masalah melibatkan 𝑛 variabel desain, algoritma dasarnya adalah  



pilih titik 𝑥0 di ruang desain pilih starting vector 𝑣1 , 𝑖 = 1,2, . . . , 𝑛 (pilihan ususal adalah 𝑣𝑖 − 𝑒𝑖 , di mana 𝑒𝑖 adalah vektor satuan dalam arah koordinat 𝑥𝑖 ).  Siklus lakukan dengan 𝑖 = 1,2, . . . , 𝑛 minimalkan 𝐹(𝑥) sepanjang garis melalui 𝑥𝑖 − 1 ke arah 𝑣𝑖 . biarkan titik minimum menjadi 𝑥𝑖 di akhir lakukan 𝑣𝑛+1 ← 𝑥0 − 𝑥𝑛 (vektor ini konjugat ke 𝑣𝑛+1 yang dihasilkan pada loop sebelumnya) Minimalkan 𝐹(𝑥) sepanjang garis melalui 𝑥0 ke arah 𝑣𝑛+1. biarkan titik minimum menjadi 𝑥𝑛+1 Jika |𝑥𝑛+1 − 𝑥0 | < 𝜀 exit loop Lakukan dengan 𝑖 = 1,2, … , 𝑛







𝑣𝑖 ← 𝑣𝑖+1 (𝑣1 dibuang, vektor lain digunakan kembali) akhir lakukan siklus akhir



Powell menunjukkan bahwa vektor-vektor 𝑣1 yang dihasilkan dalam siklus berturut-turut saling konjugat, sehingga titik minimum dari permukaan kuadrat tercapai dalam siklus yang tepat. Dalam prakteknya, fungsi kelayakan kuadrat selama dapat didekati secara lokal oleh Persamaan (10.5), metode Powell akan berhasil. tentu saja, biasanya membutuhkan lebih dari 𝑛 siklus untuk mencapai fungsi nonquadratic minimum. Perhatikan bahwa diperlukan minimalisasi untuk membuat setiap arah konjugat Gambar 10.3 (a) mengilustrasikan satu siklus metode yang khas dalam ruang desain dua dimensi (𝑛 = 2). kita mulai dengan titik 𝑥0 dan vektor 𝑣1 dan 𝑣2 . kita menemukan jarak 𝑠1 yang meminimalkan 𝐹(𝑥0 + 𝑠𝑣1 ), menyelesaikan hingga titik 𝑥1 = 𝑥0 + 𝑠1 𝑣1 . Selanjutnya, kita menentukan 𝑠2 yang meminimalkan 𝐹(𝑥1 + 𝑠𝑣2 ), yang membawa kita ke 𝑥2 = 𝑥1 + 𝑠2 𝑣2 . Arah pencarian terakhir adalah 𝑣3 = 𝑥2 − 𝑥0 . setelah menemukan 𝑠3 dengan meminimalkan 𝐹(𝑥0 + 𝑠𝑣3 ) kita mendapatkan 𝑥3 = 𝑥0 + 𝑠3 𝑣3 , menyelesaikan siklus.



Gambar 10.3 (b) menunjukkan gerakan yang dilakukan dalam dua siklus yang dilapiskan pada peta kontur permukaan kuadrat. seperti yang dijelaskan sebelumnya, siklus pertama dimulai pada titik 𝑃0 dan berakhir pada 𝑃3 . siklus kedua membawa kita ke 𝑃6 , yang merupakan titik polinomial. arah 𝑃0 𝑃3 dan 𝑃3 𝑃6 saling konjugasi. Metode Powell memang memiliki cacat besar yang harus diperbaiki-jika 𝐹(𝑥) bukan kuadrat, algoritma cenderung menghasilkan arah pencarian yang secara bertahap menjadi bergantung secara linier, sehingga merusak kemajuan menuju minimum. sumber masalahnya adalah pembuangan 𝑣1 secara otomatis pada akhir setiap siklus. Telah disarankan bahwa lebih baik untuk membuang arah yang menghasilkan penurunan 𝐹(𝑥) terbesar, kebijakan yang kita adopsi. Tampaknya berlawanan dengan intuisi untuk membuang arah terbaik, tetapi kemungkinan akan dekat dengan arah yang ditambahkan pada siklus berikutnya, sehingga berkontribusi pada ketergantungan linear. sebagai akibat dari perubahan, arah pencarian



berhenti menjadi saling konjugat, sehingga bentuk kuadrat tidak diminimalkan dalam siklus lagi. Ini bukan kerugian yang signifikan karena dalam prakteknya 𝐹(𝑥) jarang kuadratik pula. Powell menyarankan beberapa perbaikan lain untuk mempercepat konvergensi. karena ini mempersulit pembukuan secara signifikan, kami tidak mengimplementasikannya. Algoritma untuk metode Powell tercantum di bawah ini. Ini menggunakan dua aturan: df berisi penurunan fungsi yang sesuai dalam langkah pertama 𝑛 dari siklus, dan matriks u menyimpan vektor arah yang sesuai 𝑣𝑖 (satu vektor per kolom) Function [xMin, fMin, nCyc]=powell(h,tol) %Powell’s method for minimizing f(x1,x2,…,xn) %USAGE: [xMin, fMin, nCyc]=powell(h,tol) %INPUT: %h=initial search increment (default=0.1) %tol=error tolerance (default=1.0e-6) %GLOBALS (mus be declared GLOBAL in calling program) %X=starting point %FUNC=handle of function that returns f %OUTPUT: %xMin=minimum point %fMin=minimum value of f %nCyc=number of cycles to convergence Global X FUNC V If nargin>xMin= 1.000 1.000 fMin= 1.0072e-024 numCycles= 12



Contoh 10.4 Gunakan powell untuk menentukan jarak terkecil dari titik (5,8) ke kurva 𝑥𝑦 = 5 Solusi Ini adalah masalah optimisasi yang dibatasi: minimalkan 𝐹(𝑥, 𝑦) = (𝑥 − 5)2 + (𝑦 − 8)2 (kuadrat jarak) yang bergantung pada batasan kesetaraan 𝑥𝑦 − 5 = 0. Program berikut menggunakan metode Powell dengan fungsi penalti: %Example 10.4 (Powell’s method of minimization) Global X FUNC FUNC=@fex10_4; X=[1.0;5.0]; [xMin,fMin,nCyc]=powell; fprintf(‘Intersection point=%8.5f %8.5f\n’, X(1), X(2)) xy=X(1)*X(2); fprintf(‘Constraint x*y=%8.5f\n’, xy) dist=sqrt((X(1)-5.0)^2+(X(2)-8.0)^2); fprintf(‘Distance=%8.5f\n’, dist) fprintf(‘Number of cycles=%2.0f’, nCyc)



Penalti dimasukkan dalam M-file dari fungsi yang harus diminimalkan: function y=fex10_4(X) %Function used in Example 10.4 lam=1.0; %Penalty multiplier c=X(1)*X(2)-5.0; %Constraint equation distSq=(X(1)-5.0)^2+(X(2)-8.0)^2; y=distSq+lam*c^2;



Seperti disebutkan sebelumnya, nilai fungsi penalti pengganda 𝜆 (disebut lam dalam program) dapat memiliki efek mendalam pada hasil. Kita memilih 𝜆 = 1 (seperti yang ditunjukkan dalam daftar fex10_4) dengan hasil sebagai berikut: >>Intersection point= 0.73307 7.58776 Constraint x*y=5.56234



Distance=4.28680 Number of cycles=7



Nilai kecil 𝜆 favored kecepatan konvergensi atas akurasi. Karena pelanggaran kendala 𝑥𝑦 = 5 jelas tidak dapat diterima, kami menjalankan program lagi dengan 𝜆 = 10000 dan mengubah titik awal ke (0,73307, 7,58776), titik akhir dari run pertama. Hasil yang ditunjukkan di bawah sekarang dapat diterima. >>Intersection point= 0.65561 7.62654 Constraint x*y=5.00006 Distance=4.36041 Number of cycles=4



Bisakah kita menggunakan 𝜆 = 10000 di run pertama? Dalam hal ini kita akan beruntung dan mendapatkan minimum dalam 17 siklus. Oleh karena itu, kami hanya menyimpan enam siklus dengan menggunakan dua kali run. Namun, besar 𝜆 sering menyebabkan algoritma menggantung, sehingga biasanya bijaksana untuk memulai dengan 𝜆 yang kecil.