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

Video ini membahas metode Quasi-Newton untuk optimisasi nonlinear. Metode ini merupakan kompromi antara kecepatan metode Exact Newton dan biaya rendah metode steepest descent. Dengan pendekatan tanpa menghitung hessian, Quasi-Newton mencari matriks B yang mendekati inverse dari hessian untuk digunakan dalam iterasi. Terdapat beberapa metode update B yang direkomendasikan, di antaranya SR1, DFP, dan DFGS. Meskipun Quasi-Newton kalah dari Exact Newton dalam laju konvergensi, namun lebih cepat daripada steepest descent dengan biaya yang lebih optimal. Metode ini memiliki konvergensi super linear, mendekati Newton yang kuadratik, dan cocok untuk optimisasi unconstraint sebelum beralih ke persoalan constraint.

Sejauh ini kita sudah mempelajari dua metode untuk menyelesaikan optimisasi non-linear yang tak berkendala.

Yang pertama adalah metode Newton yang seringkali kita sebut sebagai Exact Newton.

Jadi Exact Newton, basically dia menggunakan prinsip bahwa titik yang baru itu sama dengan titik yang lama,

kemudian dikurangi dengan hessian inverse atau inverse dari hessian dikalikan dengan gradient atau G di titik yang sebelumnya.

Jadi hessian maupun G atau gradient itu kita hitung di titik sebelumnya.

Nah, persoalan dengan metode Exact Newton ini ada dua.

Pertama adalah kita harus mencari hessian, matriknya yang tentu saja lumayan mahal melibatkan n kwadrat pemanggilan fungsi.

Fungsi objektifnya harus kita panggil n kwadrat kali karena entrinya sebanyak n kwadrat.

Sisi lain adalah ada persamaan aljabar, meskipun kita tidak akan mencari inverse,

tapi kita membutuhkan menyelesaikan suatu sistem persamaan linier, sehingga ini akan menjadi suatu faktor yang kita perlu cari.

Sementara, metode steepest descent itu sama sekali tidak menggunakan hessian, dia hanya menggunakan gradient saja.

Dan kita sudah tunjukkan tadi bahwa itu cukup lambat.

Di satu pihak, metode Exact Newton itu bagus, cepat, tapi mahal dalam artian competitionally sangat expensive.

Metode steepest descent itu murah, tapi kalau dihitung overall juga menjadi mahal karena jumlah iterasinya akan tinggi.

Untuk itu dicari komprominya, dan ini dikenal dengan metode Quasi-Newton.

Jadi dia mencoba untuk mendekati teknik ataupun logika dari metode Newton,

tapi tanpa menghitung hessian, apalagi mencari inverse atau sistem persamaan liniernya.

Nah, idenya adalah, dia akan dibangkitkan, jadi dibangkitkan barisan matrik

yang akan converging ke inverse dari hessian kita.

Jadi hessian inverse di titik terakhir, jadi pada saat kita makin mendekati solusi x star,

maka barisan matrik kita akan makin mendekati H inverse ini.

Jadi barisan tersebut kita namakan matrik tersebut, seringkali disebut dengan matrik B,

katakanlah BK, jadi artinya, semakin besar K, maka nilai matrik B ini akan makin mendekati hessian inverse.

Nah, akibatnya apa? Kita akan memanfaatkan B ini sebagai pengganti H inverse dalam konteks Newton ini.

Nah, tapi tentu saja ada tambahan dalam hal ini bahwa kita tidak bisa menggunakan step length yang selalu satu,

tapi kita akan mengkombinasikannya dengan teknik yang tadi kita bicarakan di step-length A atau alpha,

kita harus mencari menggunakan line search, supaya dia memberikan titik terendah searah alpha pada arah G tersebut.

So, metode kuasa Newton, basically, bentuk iterasinya adalah X yang baru sama dengan X yang lama,

dikurang dengan A, dimana alpha ini adalah secara line search, kemudian ini BK atau B1,

kalau ini saya pakai X0, ini adalah B0, kalikan dengan G X0.

Nah, tentu saja kalau ini saya ganti dengan n plus 1, ini akan sama dengan n, dan ini akan sama dengan n,

ini akan indeksnya n, berarti X yang ke n plus 1 sama dengan Xn dikurang alpha, kalikan Bn dikali G Xn.

Nah, ini struktur ataupun skema iterasi dari metode kuasa Newton.

Nah, alpha tentu saja harus dicari dengan, dicari menggunakan line search yang tadi sudah kita bicarakan.

Sementara, mula-mula, jadi B yang pertama kali, B0, itu cukup kita ambil matrik identitas.

Jadi, untuk iterasi yang pertama dia steepest descent sebetulnya, karena ini minus G itu kan sama dengan P.

Jadi, kemarin kan yang disebut dengan steepest descent adalah X1 sama dengan X0 ditambah alpha P.

Jadi, kalau pada saat P saya ganti dengan minus G, berarti persis sama.

Untuk mula-mula, metode kuasa Newton ini itu persis sama dengan metode steepest descent.

Tapi, untuk iterasi berikutnya nilai B ini akan kita update.

Nah, bagaimana cara meng-update matrik B?

Itu ada tiga opsi yang banyak dipakai dan direkomendasikan, meskipun ini sebetulnya yang terakhir, yang dianggap paling baik.

Jadi, yang pertama itu dikenal dengan DFP, oh sorry, SR1.

Ini yang pertama kali sebetulnya di-introduce.

Jadi, ada arat rumusnya tersendiri, nanti akan kita tunjukkan dari slide.

Ini singkatan dari nama penemunya atau yang mengusulkan D-nya Davidon, F-nya Fletcher, dan P-nya Powell.

Nah, tiga orang ini mengusulkan sebagai perbaikan dari SR1.

Jadi, SR1 itu pertama kali di-introduce, kemudian diperbaiki oleh tiga orang ini mengusulkan DFP.

Dan yang ketiga itu yang disebut dengan DFGS.

Ada empat orang memperbaiki skema update B oleh tiga orang.

Sebelumnya Davidon, Fletcher, dan Powell.

Fletcher tetap ikut, tapi ada tiga orang baru, yaitu Broyden, Fletcher, Goldfarb, dan Shano.

Jadi, empat orang ini meng-introduce yang paling baru.

Dan inilah yang direkomendasikan saat ini untuk diterapkan meng-update B dari B1, AB0, B1, B2, dan seterusnya.

Jadi, rumus yang mereka berikan adalah bagaimana meng-update B dari B yang ke K plus 1 apabila diketahui B yang sebelumnya.

Kita tidak akan implementasikan di Octave untuk Quasi-Newton.

Tapi, kalau kita lihat, Quasi-Newton ini akan kinerjanya terletak di antara Exact-Newton.

Jadi, dia pasti akan kalah dengan Exact-Newton dari sisi laju konvergensinya.

Tapi, dia akan lebih cepat daripada Stipples Descent dari sisi laju konvergensi.

Namun, overall cost-nya dia yang paling optimum.

Karena dia hanya menggunakan matriks sekali vektor.

Dan ini dari sisi konvergens rate-nya akan mendekati Newton yang kuadratik.

Sementara, Stipples Descent itu kita sering sebut sebagai linearly convergent.

Jadi, konvergensi secara quadratic, maka Quasi-Newton ini dia super linear.

Jadi, dia tidak sampai quadratic, tapi dia lebih tinggi, lebih baik daripada linear.

Nah, sekarang kita sudah menyelesaikan untuk persoalan optimisasi tak berkendala atau unconstraint.

Selanjutnya, kita akan masuk ke topik penyelesaian untuk yang constraint.