Sidang Tugas Akhir

Kiki Septiani
g54100017

Perbandingan Eksekusi Waktu Metode Steepest Descent Dan Metode Barzilai Borwein Menggunakan MATLAB

Pengoptimuman bertujuan untuk mencari nilai minimum atau maksimum dari suatu fungsi bernilai riil. Secara umum, ada dua jenis pengoptimuman yang sering dihadapi, yaitu pengoptimuman linear dan pengoptimuman nonlinear. Masalah pengoptimuman terdiri dari fungsi tujuan dan kendala, jika kendalanya tidak ada maka masalah pengoptimuman tersebut dinamakan masalah pengoptimuman tak berkendala sebaliknya jika kendalanya ada maka masalah pengoptimuman tersebut dinamakan pengoptimuman berkendala. Masalah pengoptimuman tak berkendala satu variabel dapat diselesaikan dengan menggunakan kalkulus. Selama lebih dari empat puluh tahun telah banyak algoritme pencarian langsung (direct search) untuk masalah pengoptimuman tak berkendala yang dikembangkan. Algoritme-algoritme ini memerlukan titik awal yang dinyatakan x_0 untuk memulai proses pencarian solusi optimal langsung dari titik x_0 menuju x_1,〖 x〗_2,x_3 dan seterusnya. Proses akan berhenti jika tidak diperoleh titik yang lebih baik (lebih kecil nilai fungsinya, untuk masalah minimisasi) atau jika diperoleh titik x_k sehingga ∇f(x_k)≈0, atau dengan kriteria pemberhentian lainnya. Beberapa metode pencarian langsung untuk minimisasi fungsi satu variabel, yaitu metode golden section, metode Newton, dan algoritme interpolasi kuadratik Powell. Metode steepest descent merupakan salah satu metode klasik untuk menyelesaikan masalah pengoptimuman tak berkendala fungsi banyak variabel. Untuk beberapa kasus kekonvergenan dari metode steepest descent menuju ke solusi optimal lambat, hal ini terjadi karena jalur zig-zag dalam menuju solusi optimal (Sun dan Yuan 2006). Barzilai dan Borwein memperkenalkan dua stepsize yang menjamin konvergensi superlinear dan melakukannya cukup baik. Metode Barzilai Borwein nonmonoton, sehingga tidak mudah digeneralisasi untuk fungsi nonlinear umum kecuali teknik nonmonoton tertentu yang diterapkan. Metode Barzilai Borwein bertujuan untuk mempercepat konvergensi metode steepest descent. Metode Barzilai Borwein cukup baik untuk masalah dengan dimensi tinggi (Barzilai dan Borwein 1988). Dalam karya ilmiah ini dibahas perbandingan waktu eksekusi dan banyaknya iterasi antara metode steepest descent dan metode Barzilai Borwein dengan bantuan sofware MATLAB.