Frank – Wolfeův algoritmus - Frank–Wolfe algorithm

The Frank – Wolfeův algoritmus je iterativní první objednávka optimalizace algoritmus pro omezený konvexní optimalizace. Také známý jako metoda podmíněného přechodu,^[1] algoritmus sníženého gradientu a konvexní kombinační algoritmus, metodu původně navrhl Marguerite Frank a Philip Wolfe v roce 1956.^[2] V každé iteraci považuje algoritmus Frank – Wolfe a lineární aproximace objektivní funkce a pohybuje se směrem k minimalizátoru této lineární funkce (převzaté ve stejné doméně).

Problémové prohlášení

Předpokládat ${ displaystyle { mathcal {D}}}$ je kompaktní konvexní sada v vektorový prostor a ${ displaystyle f colon { mathcal {D}} to mathbb {R}}$ je konvexní, rozlišitelný funkce se skutečnou hodnotou. Algoritmus Frank-Wolfe řeší optimalizační problém

Minimalizovat ${ displaystyle f ( mathbf {x})}$

podléhá ${ displaystyle mathbf {x} v { mathcal {D}}}$.

Algoritmus

Krok algoritmu Frank-Wolfe

Inicializace: Nechat ${ displaystyle k leftarrow 0}$a nechte ${ displaystyle mathbf {x} _ {0} !}$ být v jakémkoli bodě ${ displaystyle { mathcal {D}}}$.

Krok 1. Dílčí problém s určováním směru: Nalézt ${ displaystyle mathbf {s} _ {k}}$ Řešení

Minimalizovat ${ displaystyle mathbf {s} ^ {T} nabla f ( mathbf {x} _ {k})}$

S výhradou ${ displaystyle mathbf {s} v { mathcal {D}}}$

(Interpretace: Minimalizujte lineární aproximaci problému daného prvním řádem Taylorova aproximace z ${ displaystyle f}$ kolem ${ displaystyle mathbf {x} _ {k} !}$.)

Krok 2. Určení velikosti kroku: Soubor ${ displaystyle gamma leftarrow { frac {2} {k + 2}}}$, nebo alternativně najít ${ displaystyle gamma}$ který minimalizuje ${ displaystyle f ( mathbf {x} _ {k} + gamma ( mathbf {s} _ {k} - mathbf {x} _ {k}))}$ podléhá ${ displaystyle 0 leq gamma leq 1}$ .

Krok 3. Aktualizace: Nechat ${ displaystyle mathbf {x} _ {k + 1} leftarrow mathbf {x} _ {k} + gamma ( mathbf {s} _ {k} - mathbf {x} _ {k})}$, nechť ${ displaystyle k leftarrow k + 1}$ a přejděte ke kroku 1.

Vlastnosti

Zatímco konkurenční metody jako klesání pro omezenou optimalizaci vyžadují a krok projekce zpět na proveditelnou množinu v každé iteraci potřebuje algoritmus Frank-Wolfe řešení lineárního problému přes stejnou množinu v každé iteraci a automaticky zůstane v proveditelné množině.

Konvergence Frank-Wolfeova algoritmu je obecně sublimní: chyba objektivní funkce k optimálnímu je ${ displaystyle O (1 / k)}$ po k iterace, pokud je přechod Lipschitz kontinuální s ohledem na nějakou normu. Stejnou míru konvergence lze také zobrazit, pokud jsou dílčí problémy vyřešeny pouze přibližně.^[3]

Iteráty algoritmu lze vždy představovat jako řídkou konvexní kombinaci extrémních bodů proveditelné množiny, což pomohlo popularitě algoritmu pro řídkou chamtivou optimalizaci v strojové učení a zpracování signálu problémy,^[4] stejně jako například optimalizace toky minimálních nákladů v dopravní sítě.^[5]

Pokud je proveditelná množina dána množinou lineárních omezení, pak se dílčí problém, který má být vyřešen v každé iteraci, stává lineární program.

Zatímco nejhorší míra konvergence s ${ displaystyle O (1 / k)}$ nelze obecně zlepšit, lze dosáhnout rychlejší konvergence pro speciální třídy úloh, jako jsou některé silně konvexní problémy.^[6]

Dolní hranice hodnoty řešení a analýza primal-dual

Od té doby ${ displaystyle f}$ je konvexní, za jakékoli dva body ${ displaystyle mathbf {x}, mathbf {y} v { mathcal {D}}}$ my máme:

${ displaystyle f ( mathbf {y}) geq f ( mathbf {x}) + ( mathbf {y} - mathbf {x}) ^ {T} nabla f ( mathbf {x})}$

To platí i pro (neznámé) optimální řešení ${ displaystyle mathbf {x} ^ {*}}$. To znamená, ${ displaystyle f ( mathbf {x} ^ {*}) geq f ( mathbf {x}) + ( mathbf {x} ^ {*} - mathbf {x}) ^ {T} nabla f ( mathbf {x})}$. Nejlepší dolní mez vzhledem k danému bodu ${ displaystyle mathbf {x}}$ je dána

${ displaystyle { begin {zarovnáno} f ( mathbf {x} ^ {*}) & geq f ( mathbf {x}) + ( mathbf {x} ^ {*} - mathbf {x}) ^ {T} nabla f ( mathbf {x}) & geq min _ { mathbf {y} v D} vlevo {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} v D} mathbf {y} ^ {T} nabla f ( mathbf {x}) end {zarovnáno}}}$

Druhý problém s optimalizací je řešen při každé iteraci Frank-Wolfeova algoritmu, tedy řešení ${ displaystyle mathbf {s} _ {k}}$ zaměřovacího dílčího problému ${ displaystyle k}$-tou iteraci lze použít ke stanovení zvyšujících se dolních mezí ${ displaystyle l_ {k}}$ během každé iterace nastavením ${ displaystyle l_ {0} = - infty}$ a

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

Takové dolní hranice neznámé optimální hodnoty jsou v praxi důležité, protože je lze použít jako kritérium zastavení a poskytnout efektivní certifikát kvality přiblížení v každé iteraci, protože vždy ${ displaystyle l_ {k} leq f ( mathbf {x} ^ {*}) leq f ( mathbf {x} _ {k})}$.

Ukázalo se, že to odpovídá rozdíl v dualitě, to je rozdíl mezi ${ displaystyle f ( mathbf {x} _ {k})}$ a dolní mez ${ displaystyle l_ {k}}$, klesá se stejnou mírou konvergence, tj.${ displaystyle f ( mathbf {x} _ {k}) - l_ {k} = O (1 / k).}$

Poznámky

Bibliografie

• Jaggi, Martin (2013). „Revisiting Frank – Wolfe: Projection-Free Sparse Convex Optimization“. Journal of Machine Learning Research: Workshop and Conference Proceedings. 28 (1): 427–435. (Přehledový papír)
• Algoritmus Frank-Wolfe popis
• Nocedal, Jorge; Wright, Stephen J. (2006). Numerická optimalizace (2. vyd.). Berlín, New York: Springer-Verlag. ISBN  978-0-387-30303-1.CS1 maint: ref = harv (odkaz).

externí odkazy

• Marguerite Frank dává osobní popis historie algoritmu

Viz také

• Metody proximálního gradientu