Frank-Wulf algoritm

Frank-Wulff-algoritmen [1] är en iterativ första ordningens optimeringsalgoritm för konvex optimering med begränsningar . Algoritmen är också känd som den villkorliga gradientmetoden [2] , den reducerade gradientmetoden och den konvexa kombinationsalgoritmen . Metoden föreslogs ursprungligen av Marguerite Frank och Philip Wolf 1956 [3] . Vid varje iteration överväger Frank-Wulff-algoritmen en linjär approximation av objektivfunktionen och rör sig i riktning mot att minimera denna linjära funktion (på samma uppsättning möjliga lösningar).

Problemformulering

Antag att det är en kompakt konvex uppsättning i ett vektorrum , och är en konvex , differentierbar verkligt värderad funktion av . Frank-Wulff-algoritmen löser optimeringsproblemet $\mathcal{D}$ $f\colon {\mathcal {D}}\to \mathbb {R}$

Minimera

f(\mathbf {x} )

tillhandahålls .

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

Algoritm

Initialisering: Låt och låt vara en punkt i .

k\leftarrow 0

\mathbf {x} _{0}\!

\mathcal{D}

Steg 1. Underuppgift för riktningssökning: Hitta , lös problemet

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

Minimera

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

under förhållanden

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

(Tolkning: Vi minimerar den linjära approximationen av problemet som erhålls genom den första ordningens Taylor-approximation av funktionen nära .)

f

\mathbf {x} _{k}\!

Steg 2. Bestämma stegstorleken: Låt , eller alternativt hitta , vilket minimerar under villkoret .

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

\gamma

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

0 \leqslant \gamma \leqslant 1

Steg 3. Omräkning: Ställ in och gå till steg 1.

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

k\leftarrow k+1

Egenskaper

Medan konkurrerande metoder, såsom gradientnedstigning för begränsad optimering, kräver att varje iteration projicerar in i en uppsättning tillåtna värden, behöver Frank-Wulf-algoritmen bara lösa ett linjärt programmeringsproblem på samma uppsättning vid varje iteration, så lösningen förblir alltid i uppsättningen möjliga lösningar.

Konvergensen av Frank-Wulf-algoritmen är i allmänhet sublinjär - felet för objektivfunktionen med avseende på det optimala värdet är efter k iterationer, förutsatt att gradienten är Lipschitz kontinuerlig i någon norm. Samma konvergens kan visas om delproblemen endast löses ungefär [4] . $O(1/k)$

Algoritmens iterationer kan alltid representeras som en icke-tät konvex kombination av extrema punkter i uppsättningen av genomförbara lösningar, vilket har hjälpt algoritmens popularitet för glesa giriga optimeringsproblem inom maskininlärning och signalbehandling [5] , som samt för att hitta minimikostnadsflöden i transportnät [6] .

Om uppsättningen av möjliga lösningar ges av en uppsättning linjära olikheter, blir delproblemet som löses vid varje iteration ett linjärt programmeringsproblem .

Även om den värsta konvergenshastigheten för det allmänna fallet inte kan förbättras, kan högre konvergenshastigheter erhållas för speciella problem såsom strikt konvexa problem [7] . $O(1/k)$

Nedre gränser för värdet av en lösning och primal-dual analys

Eftersom funktionen är konvex har vi för två punkter : $f$ $\mathbf {x} ,\mathbf {y} \in {\mathcal {D))$

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

Detta gäller även för den (okända) optimala lösningen . Det vill säga . Den bästa nedre gränsen med tanke på en poäng ges av formeln $\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))

Detta sista problem löses vid varje iteration av Frank-Wulff-algoritmen, så lösningen på delproblemet att hitta riktningen vid iterationen kan användas för att bestämma ökande nedre gränser vid varje iteration genom att tilldela och ${\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}))

Sådana nedre gränser för det okända optimala värdet är mycket viktiga i praktiken, eftersom de kan användas som ett kriterium för att stoppa algoritmen och ge en effektiv indikator på kvaliteten på approximationen vid varje iteration, eftersom alltid . $l_{k}\leqslant f(\mathbf {x} ^{*})\leqslant f(\mathbf {x} _{k})$

Det har visat sig att dualitetsgapet , som är skillnaden mellan och den nedre gränsen , minskar i samma takt, d.v.s. $f(\mathbf {x} _{k})$ ${\displaystyle l_{k))$ $f(\mathbf {x} _{k})-l_{k}=O(1/k).$

Anteckningar

↑ Algoritmen utvecklades av Margarita Frank och Philip Wolf, så namnet Frank-Wulf Algorithm , som används flitigt i rysk litteratur , är felaktigt.
↑ Levitin, Polyak, 1966 , sid. 787-823.
↑ Frank och Wolfe, 1956 , sid. 95–110.
↑ Dunn och Harshbarger 1978 , sid. 432.
↑ Clarkson, 2010 , sid. 1–30.
↑ Fukushima, 1984 , sid. 169–177.
↑ Bertsekas, 1999 , sid. 215.

Litteratur

Levitin E.S., Polyak B.T. Minimeringsmetoder i närvaro av begränsningar // Zh. Vychisl. matematik. och matta. fysik - 1966. - V. 6 , nr. 5 . - doi : 10.1016/0041-5553(66)90114-5 .
Frank M., Wolfe P. En algoritm för kvadratisk programmering // Naval Research Logistics Quarterly. - 1956. - T. 3 , nr. 1–2 . — S. 95–110 . - doi : 10.1002/nav.3800030109 .
Dunn JC, Harshbarger S. Villkorliga gradientalgoritmer med stegstorleksregler för öppen loop // Journal of Mathematical Analysis and Applications. - 1978. - T. 62 , nr. 2 . - S. 432 . - doi : 10.1016/0022-247X(78)90137-3 .
Clarkson KL Coresets, sparsam girig approximation och Frank-Wolfe-algoritmen // ACM Transactions on Algorithms. - 2010. - T. 6 , nr. 4 . — S. 1–30 . - doi : 10.1145/1824777.1824783 .
En modifierad Frank-Wolfe-algoritm för att lösa trafikuppgiftsproblemet // Transportation Research Part B: Methodological. - 1984. - T. 18 , nr. 2 . - doi : 10.1016/0191-2615(84)90029-8 .
Dimitri Bertsekas. icke-linjär programmering. - Athena Scientific, 1999. - P. 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 , nr. 1 . — S. 427–435 . (Recensionsartikel)
Beskrivning av Frank-Wulf-algoritmen
Jorge Nocedal, Stephen J. Wright. Numerisk optimering. — 2:a. - Berlin, New York: Springer-Verlag , 2006. - ISBN 978-0-387-30303-1 .
Fukushima, M. (1984). "En modifierad Frank-Wolfe-algoritm för att lösa trafiktilldelningsproblemet." Transportforskning Del B: Metodologisk . 18 (2): 169-177. DOI : 10.1016/0191-2615(84)90029-8 .

Länk

Marguerite Frank ger en personlig redogörelse för algoritmens historia

Se även

Proximal gradientmetod

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powells metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering