Algoritmul Frank-Wulf

Algoritmul Frank-Wulff [1] este un algoritm iterativ de optimizare de ordinul întâi pentru optimizarea convexă cu constrângeri . Algoritmul este cunoscut și ca metoda gradientului condiționat [2] , metoda gradientului redus și algoritmul combinației convexe . Metoda a fost propusă inițial de Marguerite Frank și Philip Wolf în 1956 [3] . La fiecare iterație, algoritmul Frank-Wulff ia în considerare o aproximare liniară a funcției obiectiv și se deplasează în direcția minimizării acestei funcții liniare (pe același set de soluții fezabile).

Declarația problemei

Să presupunem că este o mulțime compactă convexă într-un spațiu vectorial și este o funcție convexă , diferențiabilă cu valoare reală a lui . Algoritmul Frank-Wulff rezolvă problema de optimizare $\mathcal{D}$ $f\colon {\mathcal {D}}\la \mathbb {R}$

Minimizați

f(\mathbf {x} )

furnizat .

\mathbf {x} \in {\mathcal {D)}

Algoritm

Inițializare: Să și să fie un punct în .

k\leftarrow 0

\mathbf {x} _{0}\!

\mathcal{D}

Pasul 1. Subsarcină de căutare a direcției: Găsiți , rezolvarea problemei

\mathbf {s} _{k)

Minimizați

\mathbf {s} ^{T}\nabla f(\mathbf {x} _{k})

in conditii

\mathbf {s} \in {\mathcal {D)}

(Interpretare: minimizăm aproximarea liniară a problemei obținute prin aproximarea Taylor de ordinul întâi a funcției de lângă .)

f

\mathbf {x} _{k}\!

Pasul 2. Determinarea mărimii pasului: Fiți , sau, alternativ, găsiți , care se minimizează în condiția .

\gamma \leftarrow {\frac {2}{k+2)}

\gamma

f(\mathbf {x} _{k}+\gamma (\mathbf {s} _{k}-\mathbf {x} _{k}))

0 \leqslant \gamma \leqslant 1

Pasul 3. Recalculare: Setați și treceți la pasul 1.

\mathbf {x} _{k+1}\leftarrow \mathbf {x} _{k}+\gamma (\mathbf {s} _{k}-\mathbf {x} _{k})

k\leftarrow k+1

Proprietăți

În timp ce metodele concurente, cum ar fi coborârea gradientului pentru optimizarea constrânsă, necesită proiectarea fiecărei iterații într-un set de valori permise, algoritmul Frank-Wulf trebuie doar să rezolve o problemă de programare liniară pe același set la fiecare iterație, astfel încât soluția rămâne întotdeauna în setul de soluţii fezabile.

Convergența algoritmului Frank-Wulf este în general subliniară - eroarea funcției obiectiv față de valoarea optimă este după k iterații, cu condiția ca gradientul să fie continuu Lipschitz într-o anumită normă. Aceeași convergență poate fi arătată dacă subproblemele sunt rezolvate doar aproximativ [4] . $O(1/k)$

Iterațiile algoritmului pot fi întotdeauna reprezentate ca o combinație convexă nedensă de puncte extreme ale setului de soluții fezabile, ceea ce a ajutat la popularitatea algoritmului pentru problemele rare de optimizare greedy în învățarea automată și procesarea semnalului [5] , ca precum și pentru găsirea fluxurilor minime de cost în rețelele de transport [6] .

Dacă setul de soluții fezabile este dat de o mulțime de inegalități liniare, atunci subproblema rezolvată la fiecare iterație devine o problemă de programare liniară .

Deși rata de convergență din cel mai rău caz pentru cazul general nu poate fi îmbunătățită, se pot obține rate de convergență mai mari pentru probleme speciale, cum ar fi problemele strict convexe [7] . $O(1/k)$

Limitele inferioare ale valorii unei soluții și analiză primal-duală

Deoarece funcția este convexă , pentru oricare două puncte avem: $f$ $\mathbf {x} ,\mathbf {y} \in {\mathcal {D)}$

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

Acest lucru este valabil și pentru soluția optimă (necunoscută) . Adică . Cea mai bună limită inferioară luând în considerare un punct este dată de formulă $\mathbf {x} ^{*}$ $f(\mathbf {x} ^{*})\geqslant f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f (\mathbf {x} )$ $\mathbf {x}$

{\begin{aligned}f(\mathbf {x} ^{*})&\geqslant f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} ) ^{T}\nabla f(\mathbf {x} )\\&\geqslant \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{aliniat))

Această ultimă problemă este rezolvată la fiecare iterație a algoritmului Frank-Wulff, astfel încât soluția subproblemei de găsire a direcției la a-a iterație poate fi utilizată pentru a determina limite inferioare crescătoare la fiecare iterație prin atribuirea și $\mathbf {s} _{k)$ $k$ $l_{k)$ $l_{0}=-\infty$

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

Asemenea limite inferioare ale valorii optime necunoscute sunt foarte importante în practică, deoarece pot fi utilizate ca criteriu pentru oprirea algoritmului și oferă un indicator eficient al calității aproximării la fiecare iterație, de când întotdeauna . $l_{k}\leqslant f(\mathbf {x} ^{*})\leqslant f(\mathbf {x} _{k})$

S-a demonstrat că decalajul de dualitate , care este diferența dintre și limita inferioară , scade în aceeași rată, i.e. $f(\mathbf {x} _{k})$ $l_{k)$ $f(\mathbf {x} _{k})-l_{k}=O(1/k).$

Note

↑ Algoritmul a fost dezvoltat de Margarita Frank și Philip Wolf, așa că denumirea de Frank-Wulf Algorithm , care este utilizat pe scară largă în literatura rusă , este eronată.
↑ Levitin, Polyak, 1966 , p. 787-823.
↑ Frank și Wolfe, 1956 , p. 95–110.
↑ Dunn și Harshbarger 1978 , p. 432.
↑ Clarkson, 2010 , p. 1–30.
↑ Fukushima, 1984 , p. 169–177.
↑ Bertsekas, 1999 , p. 215.

Literatură

Levitin E.S., Polyak B.T. Metode de minimizare în prezenţa constrângerilor // Zh. Vychisl. matematica. și mat. fizica.- 1966. - V. 6 , nr. 5 . - doi : 10.1016/0041-5553(66)90114-5 .
Frank M., Wolfe P. Un algoritm pentru programarea pătratică // Naval Research Logistics Quarterly. - 1956. - T. 3 , nr. 1–2 . — S. 95–110 . - doi : 10.1002/nav.3800030109 .
Dunn JC, Harshbarger S. Algoritmi de gradient condiționat cu reguli de dimensiune a pasului în buclă deschisă // Journal of Mathematical Analysis and Applications. - 1978. - T. 62 , nr. 2 . - S. 432 . - doi : 10.1016/0022-247X(78)90137-3 .
Clarkson KL Coresets, aproximare rară greedy și algoritmul Frank-Wolfe // ACM Transactions on Algorithms. - 2010. - T. 6 , nr. 4 . — S. 1–30 . - doi : 10.1145/1824777.1824783 .
Un algoritm Frank-Wolfe modificat pentru rezolvarea problemei de atribuire a traficului // Cercetarea transporturilor Partea B: Metodologică. - 1984. - T. 18 , nr. 2 . - doi : 10.1016/0191-2615(84)90029-8 .
Dimitri Bertsekas. programare neliniară. - Athena Scientific, 1999. - P. 215. - ISBN 978-1-886529-00-7 .
Martin Jaggi. Revizuirea lui Frank–Wolfe: Optimizare convexă spartă fără proiecție // Journal of Machine Learning Research: Workshop and Conference Proceedings. - 2013. - T. 28 , nr. 1 . — S. 427–435 . (Revizuieste articolul)
Descrierea algoritmului Frank-Wulf
Jorge Nocedal, Stephen J. Wright. Optimizare numerica. — al 2-lea. - Berlin, New York: Springer-Verlag , 2006. - ISBN 978-0-387-30303-1 .
Fukushima, M. (1984). „Un algoritm Frank-Wolfe modificat pentru rezolvarea problemei de atribuire a traficului.” Cercetare în transport Partea B: Metodologică . 18 (2): 169-177. DOI : 10.1016/0191-2615(84)90029-8 .

Link

Marguerite Frank oferă o relatare personală a istoriei algoritmului

Vezi și

Metoda gradientului proximal

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock Metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică