Metode Steepest Descent dengan Ukuran Langkah Baru untuk Pengoptimuman Nirkendala

Abstract

Masalah pengoptimuman dapat dikategorikan dalam dua bagian yaitu pengoptimuman berkendala dan pengoptimuman nirkendala. Untuk menyelesaikan permasalahan pengoptimuman nirkendala, khususnya untuk fungsi nonlinear dapat digunakan metode steepest descent. 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. Pada beberapa kasus, metode steepest descent ini memiliki kekonvergenan yang lambat menuju solusi optimum karena langkahnya berbentuk zig-zag. Hal ini menunjukkan bahwa masalah pemilihan ukuran langkah menjadi masalah penting. Penelitian tentang pencarian ukuran langkah diantaranya adalah metode Barzilai-Borwein, Alternatif Minimisasi dan metode Yuan. Penelitian ini memiliki tiga tujuan utama yaitu: (1) merekonstruksi algoritme steepest descent, Barzilai-Borwein, Alternatif Minimisasi, dan algoritme Yuan; (2) memodifikasi metode steepest descent dengan ukuran langkah baru; dan (3) membandingkan secara eksperimental output dari modifikasi algoritme dengan metode steepest descent, Barzilai-Borwein, Alternatif Minimisasi, dan Yuan untuk kasus fungsi kuadratik ditinjau dari proses iterasi dan running time. Metode dalam penelitian ini disusun melalui tiga tahap, (1) melakukan telaah pustaka metode steepest descent klasik, metode Barzilai-Borwein, metode Alternatif Minimisasi dan metode Yuan, (2) memodifikasi ukuran langkah pada metode steepest descent dengan ukuran langkah yang baru, (3) mengimplementasikan algoritme tersebut menggunakan perangkat lunak. Kemudian dilakukan pengujian dan perbandingan untuk kasus fungsi kuadratik yang dibangkitkan secara acak. Dalam penelitian ini dihasilkan dua modifikasi ukuran langkah baru disebut Algoritme (4.5) dan Algoritme (4.6). Kedua modifikasi ini merupakan gabungan dari metode steepest descent dan metode Yuan. Dari rata-rata hasil perbandingan masalah fungsi kuadratik untuk semua dimensi metode steepest descent memberikan kinerja yang buruk dibandingkan dengan metode lainnya. Selanjutnya pada masalah dengan dimensi yang kecil, metode Yuan mampu menemukan solusi nilai minimum dengan iterasi dan running time yang terkecil. Meskipun demikian Algoritme (4.5) dan (4.6) mampu menyeimbangi kecepatan metode Yuan dan mampu mengungguli hasil dari metode Barzilai-Borwein, serta metode Alternatif Minimisasi. Untuk kasus fungsi kuadratik dengan dimensi yang besar, metode Yuan memberikan hasil yang buruk. Sedangkan, Algoritme (4.5) dan (4.6) menghasilkan iterasi dan running time yang terkecil, hal ini disebabkan oleh tingkat konvergensi yang lebih cepat pada kedua metode ini.