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

Video ini membahas metode steepest descent dalam optimasi nonlinier. Metode ini melibatkan pencarian tebakan awal X0, penentuan search direction P, dan pencarian alpha yang meminimumkan nilai fungsi objektif F searah P. Langkah-langkah ini membantu menemukan titik minimum dalam fungsi objektif. Proses ini melibatkan perhitungan manual atau penggunaan teknik penyelesaian persamaan non-linear untuk mencari alpha yang optimal. Dengan line search, kita dapat mendekati titik minimum yang diinginkan tanpa perlu melakukan proses secara manual. Kesimpulannya, steepest descent adalah pendekatan yang efektif untuk mencari titik minimum dalam optimasi nonlinier.

Kita sebut metode ini sebagai metode steepest descent.

Jadi algoritmanya adalah pertama saya kasih tebakan atau ambil tebakan awal

namakan X0, kemudian tentukan faktor arah atau search direction kita

P, kita akan sama dengan minus dari grad F di titik X0.

Oke, nah kemudian saya cari alpha step length atau panjang langkah

sedemikian sehingga nilai F searah X0 ditambah alpha P itu terendah.

Jadi kita bisa bayangkan bahwa F sebagai fungsi objektif dia turun

searah P itu dia akan turun, karena tadi kita memilih P karena dia arah turun.

Tapi turun-turun tersebut itu akan punya titik di mana dia akan naik lagi.

Nah alpha yang menyebabkan kalau saya telusuri dari X0 ke arah P

nilai Fnya mulai naik lagi, nah titik terakhir dia mulai naik lagi

itulah adalah nilai alpha yang harus kita cari.

Jadi yang meminimumkan F searah P sebagai fungsi dari alpha.

Jadi ini artinya saya dapat katakan bahwa turunan pertama dari F X0 ditambah alpha P

Ini inilah alpha yang ingin kita cari, yang menyebabkan turunan terhadap alpha.

Perhatikan bahwa P ini konstan kan, udah dapat X0 juga konstan

berarti yang variable ini alpha, alphanya akan berupa variable

sehingga kita bisa turunkan terhadap alpha.

Nah setelah alpha saya punya baru sekarang saya difensikan namanya X1

itu akan sama dengan X0 ditambah alpha kali P.

Alphanya adalah hasil dari pencarian sini tadi.

Oke, nah setelah apabila kita melakukannya secara manual

maka saya bisa untuk F yang sederhana bisa mencari alpha tersebut

atau saya bisa memanfaatkan non-linear solver

atau teknik-teknik penyelesaian persamaan non-linear yang skalar.

Ini skalar alpha ini sebagai fungsi alpha dia merupakan fungsi yang skalar.

Misalnya saya punya dua variable saja Xy sama dengan X kuadrat

4X kuadrat minus Xy ditambah 2Y kuadrat minus 3X ditambah 2Y minus 7.

jadi atau saya nggak tau ellipsoid atau paraboloid

sepertinya paraboloid jadi kayak mangkok seperti ini.

Jadi saya ingin mencari berapa titik minimumnya.

Ini kan di ruang tiga dimensi kelihatan sebagai suatu permukaan saja.

Nilai F ini akan kita nilaikan Z berarti dia ketinggian

Nilai F ke arah atas kira-kira kayak gitu.

Baik, jadi pertama katakanlah saya kasih tebakan awal X0 adalah 0,0.

Saya pakai aja X0 sama Y0 sama dengan 0,0.

P tadi kan sama dengan minus dari grad F di titik 0.

Untuk itu kita cari berapa grad dari fungsi ini.

Jadi grad F itu akan sama dengan terhadap X terlebih dahulu 8X minus Y minus 3 gitu kan.

Kemudian turunkan terhadap Y adalah minus X ditambah dengan 4Y.

Sehingga di grad F 0,0 nya itu akan sama dengan ini 0, ini 0.

Jadi saya dapatkan P saya adalah 3 minus 2.

Nah selanjutnya langkah ketiga saya harus mencari alpha yang meminimumkan.

Jadi cari alpha yang meminimumkan F X0 0,0 ditambah alpha kali 3 minus 2.

Jadi ini akan sama dengan F 3 alpha minus 2 alpha.

Coba kita masukkan X nya sama dengan 3 alpha.

Jadi F alpha akan sama dengan X nya 3 alpha berarti 4 kali 9 berarti 36 alpha kwadrat.

Kemudian X kali Y minus berarti 6 kali minus berarti plus 6 alpha kwadrat.

Kemudian 2Y kwadrat berarti 8 kali alpha kwadrat.

Kemudian dikurang 3X berarti 9 alpha ditambah 2Y berarti minus 4 alpha dikurang 7.

Ini yang saya dapatkan, saya ambil semua alpha yang kwadrat.

6 tambah 8, 14 tambah 36 berarti 50 alpha kwadrat.

Saya ingin mencari alpha yang meminimumkan titik ini.

Karena saya hitung secara manual saya gampang mencari ini, turunkan saja terhadap alpha.

Jadi D F per D alpha itu kan sama dengan 100 alpha dikurang 13 sama dengan 0.

Berarti alpha sama dengan 13 per 100 atau 0,13.

Saya dapat alphanya, itu adalah yang akan meminimumkan ini.

Langkah keempat setelah saya ketemu alpha berarti saya sekarang dapat bahwa,

Langkah keempatnya yang namanya X1 itu akan sama dengan X0.

X1 Y1 itu akan sama dengan X0 Y0 ditambah dengan alpha 0,13 dikalikan dengan P yaitu 3 minus 2.

So kita dapat ini akan sama dengan 0,39 minus 0,26.

Jadi tadinya 0,0 sekarang dia sudah pindah ke sini.

Ini kita cek apakah dia sudah memenuhi minimum condition.

Artinya bahwa grad F disini sudah sama dengan 0 atau sudah kecil sekali atau belum.

Ini yang disebut dengan steepest descent.

Nah ada komplikasi sedikit disini bahwa kalau saya akan bikin code atau program Octave untuk mencari langkah ketiga.

Ini akan cukup tricky dan menyulitkan kalau kita menggunakan analytical approach seperti ini.

Jadi ada teknik untuk mencari titik minimum tersebut yang disebut dengan line search.

Jadi tanpa melakukan ini secara manual kita bisa mencari alpha yang mendekati property minimizer ini.

Intinya adalah saya ingin mencari alpha yang paling tidak pada arah P tersebut.

Dialah yang bisa diambil sebagai titik yang representatif supaya tidak naik lagi.

Dia akan turun, sudah turun sejauh itu kalau diperbesar dia akan naik lagi.

Berarti itulah alpha yang harus saya ambil.

Saya melangkah ke arah sana hanya sampai sejauh alpha saja.

Setelah itu saya harus cari titik arah yang baru.

Jadi dengan adanya X yang baru ini maka grad tadi atau arah pencariannya akan berubah.

Jadi yang tadi yang mengarah ke timur mungkin kita agak ke selatan atau kemana.

Ini kira-kira ilustrasi dari pencarian menggunakan stipples descent.