Algoritma Frank–Wolfe

Algoritma Frank–Wolfe (bahasa Inggris: Frank-Wolfe algorithm) adalah algoritma optimasi iteratif orde pertama yang digunakan untuk optimasi cembung terkendala. Juga dikenal sebagai metode gradien bersyarat, algoritma gradien tereduksi, dan algoritma kombinasi cembung. Metode ini awalnya diusulkan oleh Marguerite Frank dan Philip Wolfe pada tahun 1956. Dalam setiap iterasi, algoritma Frank–Wolfe mempertimbangkan hampiran linear dari fungsi objektif, dan bergerak menuju peminimalisasi fungsi linier ini (diambil dari domain yang sama).

 Rumusan masalah 
Misalkan  adalah himpunan cembung kompak dalam ruang vektor dan  adalah fungsi terdiferensialkan bernilai riil yang konveks dan terdiferensialkan. Algoritma Frank–Wolfe memecahkan masalah optimasi

 Minimasi 
 dengan .

 Algoritma 
ka|jmpl|Satu langkah dari algoritma Frank-Wolfe

 Inisialisasi: Misal , dan  adalah poin sembarang pada .

 Langkah 1.  Submasalah pencarian arah: Cari  yang menyelesaikan
 Minimasi 
 dengan 
 (Interpretasi: Minimasi hampiran linear dari masalah yang diberikan dari hampiran Taylor  orde pertama dari  di sekitar  yang dibatasi untuk tetap berada di dalam )

 Langkah 2.  Penentuan jumlah langkah: Tetapkan , atau dengan cara lain, mencari  yang meminimalkan dengan  .

 Langkah 3.  Perbarui:  Misalkan , dan  kemudian kembali ke langkah 1.

 Sifat-sifat 
Meskipun metode yang mirip, seperti penurunan gradien untuk optimasi terkendala membutuhkan langkah proyeksi kembali ke himpunan yang layak di setiap iterasi, algoritma Frank–Wolfe hanya membutuhkan solusi masalah linear pada himpunan yang sama di setiap iterasi, dan secara otomatis tetap berada di himpunan yang layak.

Konvergensi algoritma Frank – Wolfe secara umum bersifat sublinear: galat pada fungsi objektif hingga mencapai optimal adalah  setelah k iterasi, selama gradiennya kontinu Lipschitz terhadap suatu norma. Tingkat konvergensi yang sama juga dapat ditunjukkan jika submasalah hanya diselesaikan secara hampiran.

Iterasi algoritma selalu dapat direpresentasikan sebagai kombinasi cembung jarang dari titik-titik ekstrem dari himpunan layak, yang telah membantu popularitas algoritma ini untuk optimasi greedy jarang (sparse greedy optimization) dalam pemelajaran mesin dan pemrosesan sinyal, serta misalnya optimasi arus biaya minimum dalam jaringan transportasi.

Jika himpunan layak diberikan oleh himpunan berkendala linier, maka submasalah yang harus diselesaikan pada setiap iterasi menjadi program linier.

Sedangkan tingkat konvergensi pada kasus terburuk dengan  secara umum tidak dapat diperbaiki, konvergensi yang lebih cepat dapat diperoleh untuk kelas masalah khusus, seperti beberapa masalah yang sangat cembung.

 Batas bawah pada nilai solusi, dan analisis primal-dual 
Karena  adalah fungsi konveks, untuk dua titik sembarang,  kita mempunyai:



Hal ini juga berlaku untuk solusi optimal (yang tidak diketahui).  . Artinya,  . Batas bawah terbaik sehubungan titik tertentu  diberikan oleh



Masalah optimasi yang terakhir diselesaikan pada setiap iterasi algoritma Frank–Wolfe. Oleh karena itu, solusi  dari submasalah pencarian arah dari  Iterasi ke- dapat digunakan untuk menentukan peningkatan batas bawah  pada setiap iterasi dengan menetapkan  dan



Batas bawah pada nilai optimal yang tidak diketahui ini penting dalam praktiknya karena dapat digunakan sebagai kriteria penghentian, dan memberikan jaminan kualitas hampiran yang efisien pada setiap iterasi, karena selalu .

Telah ditunjukkan bahwa kesenjangan dualitas ini yang sesuai, artinya perbedaan antara  dan batas bawah , menurun dengan tingkat konvergensi yang sama, yaitu 

 Catatan 

 Bibliografi 

  (Overview paper)
 The Frank–Wolfe algorithm description
 .

 Pranala luar 

 https://conditional-gradients.org/: sebuah survei terkait algoritma Frank–Wolfe.
 Marguerite Frank memberikan penjelasan pribadi tentang sejarah algoritma

 Lihat juga 

 Metode gradien hampiran