Frank-Wulf algoritmus

A Frank-Wulff algoritmus [1] egy iteratív elsőrendű optimalizáló algoritmus konvex optimalizálásra megszorításokkal [ . Az algoritmust feltételes gradiens módszernek [2] , redukált gradiens módszernek és konvex kombinációs algoritmusnak is nevezik . A módszert eredetileg Marguerite Frank és Philip Wolf javasolta 1956-ban [3] . A Frank-Wulff algoritmus minden iterációnál figyelembe veszi a lineáris közelítést célfüggvényt, és ennek a lineáris függvénynek az minimalizálása irányába mozog (ugyanazon a megvalósítható megoldásokon).

Problémafelvetés

Tegyük fel, hogy ez egy kompakt konvex halmaz egy vektortérben , és egy konvex , differenciálható valós értékű függvénye . A Frank-Wulff algoritmus megoldja az optimalizálási problémát $\mathcal{D}$ $f\colon {\mathcal {D}}\to \mathbb {R}$

Minimalizálja

f(\mathbf {x} )

feltéve .

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

Algoritmus

Inicializálás: Legyen és legyen egy pont a .

k\leftarrow 0

\mathbf {x} _{0}\!

\mathcal{D}

1. lépés : Iránykeresés részfeladat: Keresse meg , a probléma megoldása

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

Minimalizálja

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

feltételek mellett

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

(Interpretáció: A közeli függvény elsőrendű Taylor-közelítésével kapott probléma lineáris közelítését minimalizáljuk .)

f

\mathbf {x} _{k}\!

2. lépés. Lépésméret meghatározása: Legyen , vagy keresse meg , amely a feltétel alatt minimalizálódik .

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

\gamma

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

0 \leqslant \gamma \leqslant 1

3. lépés : Újraszámítás: Állítsa be a lehetőséget , és folytassa az 1. lépéssel.

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

k\leftarrow k+1

Tulajdonságok

Míg a versengő módszerek, például a gradiens süllyedés a korlátozott optimalizáláshoz, megkövetelik, hogy minden iteráció a megengedett értékek halmazába legyen vetítve , a Frank-Wulf algoritmusnak csak egy lineáris programozási problémát kell megoldania ugyanazon a halmazon minden iterációnál, így a megoldás mindig megmarad. a megvalósítható megoldások halmazában.

A Frank-Wulf algoritmus konvergenciája általában szublineáris - a célfüggvény hibája az optimális értékhez képest k iteráció után következik be, feltéve, hogy a gradiens valamilyen normában Lipschitz folytonos . Ugyanez a konvergencia mutatható ki, ha a részfeladatokat csak megközelítőleg oldjuk meg [4] . $O(1/k)$

Az algoritmus iterációi mindig a megvalósítható megoldások halmazának szélső pontjainak nem sűrű konvex kombinációjaként ábrázolhatók, ami elősegítette az algoritmus népszerűségét a ritka mohó optimalizálási problémákra a gépi tanulásban és jelfeldolgozásban [5] , mivel valamint a minimális költségáramlások megtalálásához a közlekedési hálózatokban [6] .

Ha a megvalósítható megoldások halmazát lineáris egyenlőtlenségek halmaza adja meg, akkor az egyes iterációk során megoldott részprobléma lineáris programozási feladattá válik .

Bár a legrosszabb eset konvergencia rátája általános esetben nem javítható, speciális problémák, például szigorúan konvex problémák esetén magasabb konvergencia rátákat lehet elérni [7] . $O(1/k)$

A megoldás és a primál-duális elemzés értékének alsó határai

Mivel a függvény konvex , bármelyik két pontra a következőt kapjuk: $f$ $\mathbf {x} ,\mathbf {y} \in {\mathcal {D))$

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

Ez érvényes az (ismeretlen) optimális megoldásra is . Azaz . Egy pontot figyelembe véve a legjobb alsó korlátot a képlet adja meg $\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{igazított))

Ez utóbbi probléma a Frank-Wulff algoritmus minden iterációjában megoldódik, így az i-edik iterációnál az irány megtalálásának részprobléma megoldása felhasználható az egyes iterációknál növekvő alsó határok meghatározására azáltal, hogy ill . ${\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}))

Az ismeretlen optimális érték ilyen alsó határai nagyon fontosak a gyakorlatban, mivel az algoritmus leállításának kritériumaként használhatók, és minden iterációnál hatékonyan jelzik a közelítés minőségét, hiszen mindig . $l_{k}\leqslant f(\mathbf {x} ^{*})\leqslant f(\mathbf {x} _{k})$

Kimutatták, hogy a dualitási rés , amely az alsó és az alsó korlát közötti különbség , azonos ütemben csökken, pl. $f(\mathbf {x} _{k})$ ${\displaystyle l_{k))$ $f(\mathbf {x} _{k})-l_{k}=O(1/k).$

Jegyzetek

↑ Az algoritmust Margarita Frank és Philip Wolf fejlesztette ki, ezért az orosz irodalomban széles körben használt Frank-Wulf algoritmus elnevezés hibás.
↑ Levitin, Polyak, 1966 , p. 787-823.
↑ Frank és Wolfe, 1956 , p. 95–110.
↑ Dunn és Harshbarger 1978 , p. 432.
↑ Clarkson, 2010 , p. 1–30.
↑ Fukushima, 1984 , p. 169–177.
↑ Bertsekas, 1999 , p. 215.

Irodalom

Levitin E.S., Polyak B.T. Minimalizálási módszerek kényszerek jelenlétében // Zh. Vychisl. matematika. és mat. fizika - 1966. - V. 6 , sz. 5 . - doi : 10.1016/0041-5553(66)90114-5 .
Frank M., Wolfe P. Egy algoritmus a kvadratikus programozáshoz // Naval Research Logistics Quarterly. - 1956. - T. 3 , sz. 1–2 . – S. 95–110 . - doi : 10.1002/nav.3800030109 .
Dunn JC, Harshbarger S. Feltételes gradiens algoritmusok nyílt hurkú lépésméret-szabályokkal // Journal of Mathematical Analysis and Applications. - 1978. - T. 62 , sz. 2 . - S. 432 . - doi : 10.1016/0022-247X(78)90137-3 .
Clarkson KL Coresets, ritka mohó közelítés és a Frank-Wolfe algoritmus // ACM Transactions on Algorithms. - 2010. - T. 6 , sz. 4 . — S. 1–30 . - doi : 10.1145/1824777.1824783 .
Módosított Frank-Wolfe algoritmus a forgalmi hozzárendelési probléma megoldására // Közlekedéskutatás B rész: Módszertani. - 1984. - T. 18 , sz. 2 . - doi : 10.1016/0191-2615(84)90029-8 .
Dimitri Bertsekas. nemlineáris programozás. - Athena Scientific, 1999. - P. 215. - ISBN 978-1-886529-00-7 .
Martin Jaggi. Újra Frank–Wolfe: Projekciómentes ritka konvex optimalizálás // Journal of Machine Learning Research: Workshop and Conference Proceedings. - 2013. - T. 28 , sz. 1 . – S. 427–435 . (Cikk áttekintése)
A Frank-Wulf algoritmus leírása
Jorge Nocedal, Stephen J. Wright. Numerikus optimalizálás. — 2. - Berlin, New York: Springer-Verlag , 2006. - ISBN 978-0-387-30303-1 .
Fukushima, M. (1984). "Módosított Frank-Wolfe algoritmus a forgalmi hozzárendelési probléma megoldására." Közlekedési kutatás B rész: Módszertani . 18 (2): 169-177. DOI : 10.1016/0191-2615(84)90029-8 .

Link

Marguerite Frank személyes beszámolót tart az algoritmus történetéről

Lásd még

Proximális gradiens módszer

Optimalizálási módszerek
Egydimenziós	aranymetszet módszer Kettősség Parabola módszer Rács keresés Egységes blokkkeresési módszer Fibonacci módszer Háromszoros keresés Piyavsky módszer Strongin módszer
Nulla sorrend	Gauss módszer Nelder-Mead módszer Hook-Jeeves módszer Rosenbrock módszer Powell-módszer
Első rendelés	gradiens süllyedés Zeutendijk módszer Koordináta süllyedés Konjugált gradiens módszer Kvázi-Newtoni módszerek Levenberg-Marquardt algoritmus
másodrendű	Newton módszere Newton-Raphson módszer Broyden-Fletcher-Goldfarb-Shanno algoritmus (BFGS)
Sztochasztikus	Monte Carlo módszer Szimulált lágyítás Evolúciós algoritmusok differenciális evolúció Hangya algoritmus Részecskeraj módszer Méhtelep algoritmus Véletlenszerű séta módszer
Lineáris programozási módszerek	Simplex módszer Gomori algoritmusa Ellipszoid módszer Potenciális módszer
Nemlineáris programozási módszerek	Szekvenciális kvadratikus programozás