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,[1] algoritma gradien tereduksi, dan algoritma kombinasi cembung. Metode ini awalnya diusulkan oleh Marguerite Frank dan Philip Wolfe pada tahun 1956.[2] 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 D {\displaystyle {\mathcal {D}}} adalah himpunan cembung kompak dalam ruang vektor dan f : D → R {\displaystyle f\colon {\mathcal {D}}\to \mathbb {R} } adalah fungsi terdiferensialkan bernilai riil yang konveks dan terdiferensialkan. Algoritma Frank–Wolfe memecahkan masalah optimasi

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

Algoritma

Satu langkah dari algoritma Frank-Wolfe
Inisialisasi: Misal k ← 0 {\displaystyle k\leftarrow 0} , dan x 0 {\displaystyle \mathbf {x} _{0}\!} adalah poin sembarang pada D {\displaystyle {\mathcal {D}}} .
Langkah 1. Submasalah pencarian arah: Cari s k {\displaystyle \mathbf {s} _{k}} yang menyelesaikan
Minimasi s T ∇ f ( x k ) {\displaystyle \mathbf {s} ^{T}\nabla f(\mathbf {x} _{k})}
dengan s ∈ D {\displaystyle \mathbf {s} \in {\mathcal {D}}}
(Interpretasi: Minimasi hampiran linear dari masalah yang diberikan dari hampiran Taylor orde pertama dari f {\displaystyle f} di sekitar x k {\displaystyle \mathbf {x} _{k}\!} yang dibatasi untuk tetap berada di dalam D {\displaystyle {\mathcal {D}}} )
Langkah 2. Penentuan jumlah langkah: Tetapkan α ← 2 k + 2 {\displaystyle \alpha \leftarrow {\frac {2}{k+2}}} , atau dengan cara lain, mencari α {\displaystyle \alpha } yang meminimalkan f ( x k + α ( s k − x k ) ) {\displaystyle f(\mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k}))} dengan 0 ≤ α ≤ 1 {\displaystyle 0\leq \alpha \leq 1} .
Langkah 3. Perbarui: Misalkan x k + 1 ← x k + α ( s k − x k ) {\displaystyle \mathbf {x} _{k+1}\leftarrow \mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k})} , dan k ← k + 1 {\displaystyle 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 ) {\displaystyle 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.[3]

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

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 ) {\displaystyle O(1/k)} secara umum tidak dapat diperbaiki, konvergensi yang lebih cepat dapat diperoleh untuk kelas masalah khusus, seperti beberapa masalah yang sangat cembung.[6]

Batas bawah pada nilai solusi, dan analisis primal-dual

Karena f {\displaystyle f} adalah fungsi konveks, untuk dua titik sembarang, x , y ∈ D {\displaystyle \mathbf {x} ,\mathbf {y} \in {\mathcal {D}}} kita mempunyai:

f ( y ) ≥ f ( x ) + ( y − x ) T ∇ f ( x ) {\displaystyle 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). x ∗ {\displaystyle \mathbf {x} ^{*}} . Artinya, f ( x ∗ ) ≥ f ( x ) + ( x ∗ − x ) T ∇ f ( x ) {\displaystyle f(\mathbf {x} ^{*})\geq f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )} . Batas bawah terbaik sehubungan titik tertentu x {\displaystyle \mathbf {x} } diberikan oleh

f ( x ∗ ) ≥ f ( x ) + ( x ∗ − x ) T ∇ f ( x ) ≥ min y ∈ D { f ( x ) + ( y − x ) T ∇ f ( x ) } = f ( x ) − x T ∇ f ( x ) + min y ∈ D y T ∇ f ( x ) {\displaystyle {\begin{aligned}f(\mathbf {x} ^{*})&\geq 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{aligned}}}

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

l k := max ( l k − 1 , f ( x k ) + ( s k − x k ) T ∇ f ( x k ) ) {\displaystyle 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 ≤ f ( x ∗ ) ≤ f ( x k ) {\displaystyle l_{k}\leq f(\mathbf {x} ^{*})\leq f(\mathbf {x} _{k})} .

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

Catatan

  1. ^ Levitin, E. S.; Polyak, B. T. (1966). "Constrained minimization methods". USSR Computational Mathematics and Mathematical Physics. 6 (5): 1. doi:10.1016/0041-5553(66)90114-5. 
  2. ^ Frank, M.; Wolfe, P. (1956). "An algorithm for quadratic programming". Naval Research Logistics Quarterly. 3 (1–2): 95–110. doi:10.1002/nav.3800030109. 
  3. ^ Dunn, J. C.; Harshbarger, S. (1978). "Conditional gradient algorithms with open loop step size rules". Journal of Mathematical Analysis and Applications. 62 (2): 432. doi:10.1016/0022-247X(78)90137-3. 
  4. ^ Clarkson, K. L. (2010). "Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm". ACM Transactions on Algorithms. 6 (4): 1–30. doi:10.1145/1824777.1824783. 
  5. ^ Fukushima, M. (1984). "A modified Frank-Wolfe algorithm for solving the traffic assignment problem". Transportation Research Part B: Methodological. 18 (2): 169–177. doi:10.1016/0191-2615(84)90029-8. 
  6. ^ Bertsekas, Dimitri (1999). Nonlinear Programming. Athena Scientific. hlm. 215. ISBN 978-1-886529-00-7. 

Bibliografi

  • Jaggi, Martin (2013). "Revisiting Frank–Wolfe: Projection-Free Sparse Convex Optimization". Journal of Machine Learning Research: Workshop and Conference Proceedings. 28 (1): 427–435.  (Overview paper)
  • The Frank–Wolfe algorithm description
  • Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (edisi ke-2nd). Berlin, New York: Springer-Verlag. ISBN 978-0-387-30303-1. .

Pranala eksternal

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

Lihat juga

  • Metode gradien hampiran

Templat:Algoritma optimasi