Algoritma Frank–Wolfe: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Dibuat dengan menerjemahkan halaman "Frank–Wolfe algorithm" |
k perbaikan keluputan spasi |
||
Baris 1:
'''Algoritma Frank–Wolfe''' ([[bahasa Inggris]]: ''Frank-Wolfe algorithm'') adalah [[algoritma]] [[Optimisasi|optimasi]] [[Metode iteratif|iteratif]] [[Hampiran orde pertama|orde pertama]] yang digunakan untuk [[Optimasi konveks|optimasi cembung]] [[Optimasi terkendala|terkendala]]. Juga dikenal sebagai '''metode gradien bersyarat''',<ref>{{Cite journal|last=Levitin|first=E. S.|last2=Polyak|first2=B. T.|year=1966|title=Constrained minimization methods|journal=USSR Computational Mathematics and Mathematical Physics|volume=6|issue=5|pages=1|doi=10.1016/0041-5553(66)90114-5}}</ref> '''algoritma gradien tereduksi,''' dan '''algoritma kombinasi cembung'''
== Rumusan masalah ==
Misalkan <math>\mathcal{D}</math> adalah [[himpunan cembung]] [[Ruang kompak|kompak]] dalam [[ruang vektor]] dan <math>f \colon \mathcal{D} \to \mathbb{R}</math> adalah [[Fungsi bernilai riil|fungsi terdiferensialkan bernilai riil]] [[Fungsi konveks|yang konveks]] dan [[Fungsi terdiferensialkan|terdiferensialkan]]. Algoritma Frank–Wolfe memecahkan [[Permasalahan optimasi|masalah optimasi]]
: Minimasi <math> f(\mathbf{x})</math>
: dengan <math> \mathbf{x} \in \mathcal{D}</math>.
Baris 16:
:: Minimasi <math> \mathbf{s}^T \nabla f(\mathbf{x}_k)</math>
:: dengan <math>\mathbf{s} \in \mathcal{D}</math>
: ''(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'' <math>\alpha \leftarrow \frac{2}{k+2}</math>, atau dengan cara lain, mencari <math>\alpha</math> yang meminimalkan<math> f(\mathbf{x}_k+\alpha(\mathbf{s}_k -\mathbf{x}_k))</math> dengan <math>0 \le \alpha \le 1</math> .
: '''Langkah 3.''' ''Perbarui:'' Misalkan <math>\mathbf{x}_{k+1}\leftarrow \mathbf{x}_k+\alpha(\mathbf{s}_k-\mathbf{x}_k)</math>, dan <math>k \leftarrow k+1</math> kemudian kembali ke langkah 1.
== Sifat-sifat ==
Meskipun metode
Konvergensi algoritma Frank – Wolfe secara umum bersifat sublinear: galat pada fungsi objektif hingga mencapai optimal adalah <math>O(1/k)</math> setelah ''k'' iterasi, selama gradiennya [[Fungsi Lipschitz|kontinu Lipschitz]] terhadap suatu norma. Tingkat konvergensi yang sama juga dapat ditunjukkan jika submasalah hanya diselesaikan secara hampiran.<ref>{{Cite journal|last=Dunn|first=J. C.|last2=Harshbarger|first2=S.|year=1978|title=Conditional gradient algorithms with open loop step size rules|journal=Journal of Mathematical Analysis and Applications|volume=62|issue=2|pages=432|doi=10.1016/0022-247X(78)90137-3}}</ref>
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 [[Pengolahan sinyal|pemrosesan sinyal]],<ref>{{Cite journal|last=Clarkson|first=K. L.|year=2010|title=Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm|journal=ACM Transactions on Algorithms|volume=6|issue=4|pages=1–30|doi=10.1145/1824777.1824783}}</ref> serta misalnya optimasi [[Jaringan aliran|arus biaya minimum]] dalam [[jaringan transportasi]].<ref>{{Cite journal|last=Fukushima|first=M.|year=1984|title=A modified Frank-Wolfe algorithm for solving the traffic assignment problem|journal=Transportation Research Part B: Methodological|volume=18|issue=2|pages=169–177|doi=10.1016/0191-2615(84)90029-8}}</ref>
Jika himpunan layak diberikan oleh himpunan berkendala linier, maka submasalah yang harus diselesaikan pada setiap iterasi menjadi [[Program linear|program linier]].
Sedangkan tingkat konvergensi pada kasus terburuk dengan <math>O(1/k)</math> 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 ==
Baris 59:
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 <math>l_k \leq f(\mathbf{x}^*) \leq f(\mathbf{x}_k)</math>.
Telah ditunjukkan bahwa [[kesenjangan dualitas]] ini yang sesuai, artinya perbedaan antara <math>f(\mathbf{x}_k)</math> dan batas bawah <math>l_k</math>, menurun dengan tingkat konvergensi yang sama, yaitu <math>
f(\mathbf{x}_k) - l_k = O(1/k) .
</math>
Baris 79:
== Lihat juga ==
* [[
{{Algoritma optimasi|konveks}}
| |||