Frank-Wulfův algoritmus

Frank-Wulffův algoritmus [1] je iterativní optimalizační algoritmus prvního řádu pro konvexní optimalizaci s omezeními . Algoritmus je také známý jako metoda podmíněného gradientu [2] , metoda sníženého gradientu a algoritmus konvexní kombinace . Metodu původně navrhli Marguerite Frank a Philip Wolf v roce 1956 [3] . Při každé iteraci Frank-Wulffův algoritmus zvažuje lineární aproximaci objektivní funkce a pohybuje se ve směru minimalizace této lineární funkce (na stejné množině proveditelných řešení).

Problémové prohlášení

Předpokládejme, že je to kompaktní konvexní množina ve vektorovém prostoru a je to konvexní , diferencovatelná funkce reálné hodnoty . Problém optimalizace řeší Frank-Wulffův algoritmus $\mathcal{D}$ $f\colon {\mathcal {D}}\to \mathbb {R}$

Minimalizovat

f(\mathbf {x} )

za předpokladu .

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

Algoritmus

Inicializace: Nechť a nech být bod v .

k\leftarrow 0

\mathbf {x} _{0}\!

\mathcal{D}

Krok 1. Dílčí úkol hledání směru: Najděte , vyřešte problém

{\displaystyle \mathbf {s} _{k))

Minimalizovat

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

za podmínek

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

(Výklad: Minimalizujeme lineární aproximaci problému získaného Taylorovou aproximací prvního řádu funkce blízko .)

F

\mathbf {x} _{k}\!

Krok 2. Určení velikosti kroku: Nechte , nebo alternativně najděte , která minimalizuje pod podmínkou .

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

\gamma

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

0 \leqslant \gamma \leqslant 1

Krok 3. Přepočet: Nastavte a přejděte ke kroku 1.

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

k\leftarrow k+1

Vlastnosti

Zatímco konkurenční metody, jako je gradientní sestup pro omezenou optimalizaci, vyžadují, aby se každá iterace promítla do sady povolených hodnot, algoritmus Frank-Wulf potřebuje pouze vyřešit problém lineárního programování na stejné sadě při každé iteraci, takže řešení vždy zůstává v sadě možných řešení.

Konvergence Frank-Wulfova algoritmu je obecně sublineární - chyba účelové funkce vzhledem k optimální hodnotě je po k iteracích za předpokladu, že gradient je v nějaké normě Lipschitzův spojitý . Stejnou konvergenci lze ukázat, pokud jsou dílčí problémy vyřešeny pouze přibližně [4] . $O(1/k)$

Iterace algoritmu mohou být vždy reprezentovány jako nehustá konvexní kombinace extrémních bodů množiny proveditelných řešení, což přispělo k popularitě algoritmu pro řídké optimalizační problémy ve strojovém učení a zpracování signálů [5] , as i pro hledání minimálních nákladových toků v dopravních sítích [6] .

Pokud je množina možných řešení dána množinou lineárních nerovností, pak se dílčí problém řešený v každé iteraci stává problémem lineárního programování .

Přestože míru konvergence v nejhorším případě pro obecný případ nelze zlepšit, lze získat vyšší míru konvergence pro speciální problémy, jako jsou přísně konvexní problémy [7] . $O(1/k)$

Dolní hranice hodnoty řešení a primal-duální analýza

Protože je funkce konvexní , pro libovolné dva body máme: $F$ $\mathbf {x} ,\mathbf {y} \in {\mathcal {D))$

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

To platí i pro (neznámé) optimální řešení . To je . Nejlepší dolní mez uvažující bod je dána vzorcem $\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{aligned))

Tento poslední problém se řeší při každé iteraci Frank-Wulffova algoritmu, takže řešení dílčího problému nalezení směru v i -té iteraci lze použít k určení rostoucích dolních mezí při každé iteraci přiřazením a ${\displaystyle \mathbf {s} _{k))$ $k$ ${\displaystyle 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}))

Takové dolní meze na neznámé optimální hodnotě jsou v praxi velmi důležité, protože mohou být použity jako kritérium pro zastavení algoritmu a poskytují efektivní ukazatel kvality aproximace při každé iteraci, protože vždy . $l_{k}\leqslant f(\mathbf {x} ^{*})\leqslant f(\mathbf {x} _{k})$

Ukázalo se, že dualitní mezera , což je rozdíl mezi a spodní hranicí , klesá stejnou rychlostí, tzn. $f(\mathbf {x} _{k})$ ${\displaystyle l_{k))$ $f(\mathbf {x} _{k})-l_{k}=O(1/k).$

Poznámky

↑ Algoritmus vyvinuli Margarita Frank a Philip Wolf, takže název Frank-Wulf Algorithm , který je široce používán v ruské literatuře , je chybný.
↑ Levitin, Polyak, 1966 , str. 787-823.
↑ Frank a Wolfe, 1956 , s. 95–110.
↑ Dunn a Harshbarger 1978 , str. 432.
↑ Clarkson, 2010 , str. 1–30.
↑ Fukušima, 1984 , s. 169–177.
↑ Bertsekas, 1999 , s. 215.

Literatura

Levitin E.S., Polyak B.T. Metody minimalizace za přítomnosti omezení // Zh. Vychisl. matematika. a mat. fyzika - 1966. - V. 6 , č. 5 . - doi : 10.1016/0041-5553(66)90114-5 .
Frank M., Wolfe P. Algoritmus pro kvadratické programování // Naval Research Logistics Quarterly. - 1956. - T. 3 , čís. 1–2 . — S. 95–110 . - doi : 10.1002/nav.3800030109 .
Dunn JC, Harshbarger S. Algoritmy podmíněného gradientu s pravidly pro velikost kroku v otevřené smyčce // Journal of Mathematical Analysis and Applications. - 1978. - T. 62 , čís. 2 . - S. 432 . - doi : 10.1016/0022-247X(78)90137-3 .
Clarkson KL Coresets, řídká chamtivá aproximace a Frank-Wolfeův algoritmus // ACM Transactions on Algorithms. - 2010. - T. 6 , no. 4 . — S. 1–30 . - doi : 10.1145/1824777.1824783 .
Upravený Frank-Wolfeův algoritmus pro řešení problému dopravního zadání // Transportation Research Part B: Methodological. - 1984. - T. 18 , no. 2 . - doi : 10.1016/0191-2615(84)90029-8 .
Dimitrij Bertsekas. nelineární programování. - Athena Scientific, 1999. - S. 215. - ISBN 978-1-886529-00-7 .
Martin Jaggi. Revisiting Frank–Wolfe: Projection-Free Sparse Convex Optimization // Journal of Machine Learning Research: Workshop and Conference Proceedings. - 2013. - T. 28 , no. 1 . — S. 427–435 . (Recenze článku)
Popis Frank-Wulfova algoritmu
Jorge Nocedal, Stephen J. Wright. Numerická optimalizace. — 2. - Berlin, New York: Springer-Verlag , 2006. - ISBN 978-0-387-30303-1 .
Fukushima, M. (1984). "Upravený Frank-Wolfeův algoritmus pro řešení problému přiřazení provozu." Dopravní výzkum Část B: Metodický . 18 (2): 169-177. DOI : 10.1016/0191-2615(84)90029-8 .

Odkaz

Marguerite Frank podává osobní popis historie algoritmu

Viz také

Metoda proximálního gradientu

Optimalizační metody
Jednorozměrný	metoda zlatého řezu Dichotomie Parabolová metoda Vyhledávání v mřížce Jednotná metoda vyhledávání bloků Fibonacciho metoda Ternární hledání Piyavského metoda Stronginovou metodou
Nulové pořadí	Gaussova metoda Metoda Nelder-Mead Hook-Jeevesova metoda Rosenbrockova metoda Powellova metoda
První objednávka	gradientní sestup Zeutendijkova metoda Souřadnicový sestup Metoda konjugovaného gradientu Kvazi-newtonské metody Levenberg-Marquardtův algoritmus
druhá objednávka	Newtonova metoda Newton-Raphsonova metoda Algoritmus Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastické	Metoda Monte Carlo Simulované žíhání Evoluční algoritmy diferenciální evoluce Algoritmus mravenců Metoda roje částic Algoritmus včelstva Metoda náhodné chůze
Metody lineárního programování	Simplexní metoda Gomoriho algoritmus Elipsoidní metoda Potenciální metoda
Metody nelineárního programování	Sekvenční kvadratické programování