Prof. Drs. T. Basaruddin, Ph.D.

Video ini membahas implementasi algoritma line search dan steepest descent dalam optimasi nonlinier menggunakan Octave/Matlab. Algoritma line search digunakan untuk mencari step length atau learning rate dalam pencarian titik optimum fungsi objektif. Teknik bisection digunakan untuk mencari nilai optimum A dengan pendekatan sederhana. Sementara itu, algoritma steepest descent digunakan untuk mencari titik optimum dengan arah pencarian searah minus dari gradient. Dengan menggunakan algoritma steepest descent, kita dapat menemukan titik optimum fungsi objektif dengan iterasi yang terbatas. Metode ini terbukti dapat memberikan hasil yang cukup akurat dalam optimasi nonlinier.

Sekarang kita akan coba implementasikan algoritma line search atau cara kita mencari step length

atau kadang-kadang disebut learning rate, A atau alpha jika diketahui X0 kemudian P sebagai arah pencarian

dan F sebagai fungsi objektif yang perlu kita cari titik optimumnya atau optimize.

Kemarin kita juga sudah melihat bahwa step length itu harus positif,

kemudian dari pengalaman empiris juga akan terletak di antara 0 dengan 1 biasanya

sehingga kita bisa menggunakan pendekatan sederhana dengan model bisection

jadi kita akan bracket atau kita kurung A tersebut di antara 0 dan 1

dengan asumsi bahwa searah P fungsinya akan turun

berarti turunan pertama di sekitar A0 atau di sekitar titik 0 itu harus negatif karena dia harus turun

dan menjelang A sama dengan 1 dia akan naik lagi berarti dia akan positif.

Nah ini kita sudah memiliki kondisi di mana nilai dari turunan di kedua ujung interval itu berbeda tanda

satu negatif satu positif sehingga dengan menggunakan intermediate value theorem

kita tahu bahwa turunan pertama tersebut pernah 0 di antara 0 dengan 1.

Nah titik itulah yang akan kita ambil sebagai optimum A

yang menyebabkan turunan pertama dari F terhadap alfa turunan pertama terhadap alfanya sama dengan 0.

Baik, jadi kita akan menggunakan teknik bisection atau squeeze

jadi kita pakai while sepanjang 1 yang disebelah kanan dikurangi dengan 0

0 itu masih lebih kecil dari suatu nilai tertentu katakanlah kita akan ambil sekitar 10 pangkat minus 10 katakanlah

Pertama kita akan cari titik tengah jadi M itu adalah titik di antara 0 dan A1

Kemudian kita akan melihat bagaimana kalau kita geser di

atau kita ingin cari sebetulnya turunan di turunan terhadap alfa terhadap A di titik M

Nah untuk itu kita akan menggeser X0 dengan giseran M plus H dan M minus H

Jadi kita definisikan X0 M plus H jadi ini akan sama dengan X0 kemudian ditambah dengan M ditambah dengan H

H sudah kita definisikan di atas 10 pangkat minus 6 dikalikan dengan P

Jadi ingat bahwa kita akan bergerak searah search direction atau arah pencarian faktor kita P

Nah kita bergerak ke kiri apa namanya dari M itu ke kanan sejauh H dan ke kiri sejauh H untuk melihat turunan pendekatan untuk turunan di sekitar titik M

Kemudian kita namakan X0 M minus H ini adalah sama dengan X0 ditambah dengan M minus H sekarang

Jadi kita akan bergerak ke kanan sejauh H dan ke kiri sejauh H searah alfa

Jadi ini turunan yang akan kita cari adalah terhadap alfa

Jadi sehingga turunan dari F di titik M kita gunakan pendekatan turunan pertama

Dikurangi dengan nilai F di titik X0 M minus H

Kemudian dibagi dengan dua kali H jadi ini adalah bentuk yang cukup akurat untuk mendekati sebuah turunan

Nah sekarang coba kita perhatikan tadi di titik A0 sebetulnya turunan itu negatif

Jadi sekarang saya mau cek apakah di titik M

Maka A1 saya itu sudah keadaan luar biasa

Artinya titik yang menyebabkan turunan pertama 0 itu sebetulnya berada di antara A0 dengan M

Jadi A1-nya kita buang, kita ganti dengan M

Maka A0-nya berarti kalau dia negatif berarti dia sama dengan di A0 sehingga A0 yang kita buang kita jadikan sama dengan M

Sudah kita akan men-squeeze interval tersebut sehingga A1 kurang A0 makin lama makin kecil

Dan dia akan berhenti di sekitar 10 bangkat minus 11 gitu ya

Sebetulnya karena A0 dan A1-nya itu mula-mula sama dengan 0 dan 1

Maka kita sudah bisa mengetahui berapa kali ini harus diputar gitu

Tergantung pada nilai dari error control ini

Jadi kalau ini kita pandang terlalu lama dia mutar

Ini bisa kita kecilin, kita besarkan misalnya gak usah minus 10 cukup minus 8

Misalnya ini juga udah oke sebetulnya gitu

Oke, terakhir tentu saja kita ingin mencari A dan A yang kita cari itu kita bisa set sama dengan M

Kita memperoleh sekarang suatu fungsi yang akan mencari line search gitu ya

Jadi misalkan dalam hal ini kita coba run dengan contoh fungsi objektif yang kita miliki

Jadi kalau kita lihat kemarin ini adalah 4X1 kawadrat

Dikurang 3X1 tambah 2X2 minus 10 misalnya ini fungsinya

Katakanlah saya berikan X0 sama dengan 10

Kemudian saya namakan P sekarang sama dengan grad dari FOBJ tadi

Kemarin kita udah bikin fungsi yang akan mencari gradient

Sekarang saya bisa mencari A dengan line search tadi

Kebetulan Pnya mestinya sama dengan minusnya

Jadi kalau gradient descent berarti minus dari grad

Oke ada kesalahan dalam penulisan fungsinya

Jadi nilai F itu akan paling minimum searah P

Dengan step length apabila kita melangkah sejauh 0,1340

Baik itu line searchnya sudah kita implementasikan

Sekarang kita akan implementasikan fungsi yang berikutnya

Atau fungsi yang akan mencari titik optimum

Dengan arah pencarian adalah arah minus dari gradient

Dimana arah tersebut merupakan arah tercuram dari penurunan P

Oke jadi struktur dari logika fungsi steepest descent ini adalah

Pertama dia akan mengeluarkan titik dimana fungsi tersebut mencapai minimum