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 \mathcal{D} adalah himpunan cembung kompak dalam ruang vektor dan f \colon \mathcal{D} \to \mathbb{R} adalah fungsi terdiferensialkan bernilai riil yang konveks dan terdiferensialkan. Algoritma Frank–Wolfe memecahkan masalah optimasi

: Minimasi  f(\mathbf{x})
: dengan  \mathbf{x} \in \mathcal{D}.

## Algoritma

: *Inisialisasi:* Misal k \leftarrow 0, dan \mathbf{x}_0 \! adalah poin sembarang pada \mathcal{D}.

: **Langkah 1.**  *Submasalah pencarian arah:* Cari \mathbf{s}_k yang menyelesaikan
:: Minimasi   \mathbf{s}^T \nabla f(\mathbf{x}_k)
:: dengan \mathbf{s} \in \mathcal{D}
: *(Interpretasi: Minimasi hampiran linear dari masalah yang diberikan dari [[Deret Taylor|hampiran Taylor]]  orde pertama dari <math>f</math> di sekitar <math>\mathbf{x}_k \!</math> yang dibatasi untuk tetap berada di dalam <math>\mathcal{D}</math>)*

: **Langkah 2.**  *Penentuan jumlah langkah: Tetapkan* \alpha \leftarrow \frac{2}{k+2}, atau dengan cara lain, mencari \alpha yang meminimalkan f(\mathbf{x}_k+\alpha(\mathbf{s}_k -\mathbf{x}_k)) dengan 0 \le \alpha \le 1 .

: **Langkah 3.**  *Perbarui:*  Misalkan \mathbf{x}_{k+1}\leftarrow \mathbf{x}_k+\alpha(\mathbf{s}_k-\mathbf{x}_k), dan k \leftarrow k+1 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 O(1/k) 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 O(1/k) 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 f adalah fungsi konveks, untuk dua titik sembarang, \mathbf{x}, \mathbf{y} \in \mathcal{D} kita mempunyai:

: 
 f(\mathbf{y}) \geq f(\mathbf{x}) + (\mathbf{y} - \mathbf{x})^T \nabla f(\mathbf{x})


Hal ini juga berlaku untuk solusi optimal (yang tidak diketahui). \mathbf{x}^* . Artinya, f(\mathbf{x}^*) \ge f(\mathbf{x}) + (\mathbf{x}^* - \mathbf{x})^T \nabla f(\mathbf{x}) . Batas bawah terbaik sehubungan titik tertentu \mathbf{x} diberikan oleh

: 
 \begin{align}
f(\mathbf{x}^*) 
& \ge f(\mathbf{x}) + (\mathbf{x}^* - \mathbf{x})^T \nabla f(\mathbf{x}) \\ 
&\geq \min_{\mathbf{y} \in D} \left\{ f(\mathbf{x}) + (\mathbf{y} - \mathbf{x})^T \nabla f(\mathbf{x}) \right\} \\
&= f(\mathbf{x}) - \mathbf{x}^T \nabla f(\mathbf{x}) + \min_{\mathbf{y} \in D} \mathbf{y}^T \nabla f(\mathbf{x})
\end{align}


Masalah optimasi yang terakhir diselesaikan pada setiap iterasi algoritma Frank–Wolfe. Oleh karena itu, solusi \mathbf{s}_k dari submasalah pencarian arah dari  Iterasi ke-k dapat digunakan untuk menentukan peningkatan batas bawah l_k pada setiap iterasi dengan menetapkan l_0 = - \infty dan

: 
 l_k := \max (l_{k - 1}, f(\mathbf{x}_k) + (\mathbf{s}_k - \mathbf{x}_k)^T \nabla f(\mathbf{x}_k))


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 l_k \leq f(\mathbf{x}^*) \leq f(\mathbf{x}_k).

Telah ditunjukkan bahwa kesenjangan dualitas ini yang sesuai, artinya perbedaan antara f(\mathbf{x}_k) dan batas bawah l_k, menurun dengan tingkat konvergensi yang sama, yaitu 
 f(\mathbf{x}_k) - l_k = O(1/k) .


## 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