Frank-Wulf algoritmi

Frank-Wulff-algoritmi [1] on iteratiivinen ensimmäisen kertaluvun optimointialgoritmi konveksia optimointia varten rajoituksilla [ . Algoritmi tunnetaan myös ehdollisena gradienttimenetelmänä [2] , pelkistetyn gradientin menetelmänä ja konveksina yhdistelmäalgoritmina . Menetelmää ehdottivat alun perin Marguerite Frank ja Philip Wolf vuonna 1956 [3] . Jokaisessa iteraatiossa Frank-Wulff-algoritmi harkitsee tavoitefunktion lineaarista approksimaatiota ja liikkuu tämän lineaarisen funktion minimoimisen suuntaan (samalla mahdollisilla ratkaisuilla).

Ongelman kuvaus

Oletetaan, että se on kompakti kupera joukko vektoriavaruudessa ja on konveksi , differentioituva reaaliarvoinen funktio . Frank-Wulff-algoritmi ratkaisee optimointiongelman $\mathcal{D}$ $f\colon {\mathcal {D}}\to \mathbb {R}$

Minimoida

f(\mathbf {x} )

tarjotaan .

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

Algoritmi

Alustus: Antaa ja antaa olla kohta .

k\leftarrow 0

\mathbf {x} _{0}\!

\mathcal{D}

Vaihe 1. Suuntahaun alitehtävä: Etsi , ratkaisee ongelman

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

Minimoida

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

olosuhteissa

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

(Tulkinta: Minimoimme tehtävän lineaarisen approksimation, joka saadaan funktion lähellä :n ensimmäisen asteen Taylor-approksimaatiolla .)

f

\mathbf {x} _{k}\!

Vaihe 2. Askelkoon määrittäminen: Anna , tai vaihtoehtoisesti etsi , joka minimoi ehdolla .

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

\gamma

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

0 \leqslant \gamma \leqslant 1

Vaihe 3. Uudelleenlaskenta: Aseta ja siirry vaiheeseen 1.

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

k\leftarrow k+1

Ominaisuudet

Kun kilpailevat menetelmät, kuten gradienttilaskeutuminen rajoitettua optimointia varten, vaativat jokaisen iteroinnin projisoitumaan sallittujen arvojen joukkoon, Frank-Wulf-algoritmin tarvitsee vain ratkaista lineaarinen ohjelmointiongelma samassa sarjassa jokaisessa iteraatiossa, joten ratkaisu säilyy aina. toteuttamiskelpoisten ratkaisujen joukossa.

Frank-Wulf-algoritmin konvergenssi on yleensä sublineaarinen - tavoitefunktion virhe suhteessa optimaaliseen arvoon on k iteroinnin jälkeen , mikäli gradientti on Lipschitzin jatkuva jossain normissa. Sama konvergenssi voidaan osoittaa, jos osaongelmat ratkaistaan vain suunnilleen [4] . $O(1/k)$

Algoritmin iteraatiot voidaan aina esittää ei-tiheänä kuperana yhdistelmänä toteutettavissa olevien ratkaisujen joukon ääripisteitä, mikä on edistänyt algoritmin suosiota harvaan ahneisiin optimointiongelmiin koneoppimisessa ja signaalinkäsittelyssä [5] , koska sekä vähimmäiskustannusvirtojen löytämiseen liikenneverkoissa [6] .

Jos toteutettavissa olevien ratkaisujen joukko annetaan lineaaristen epäyhtälöiden joukolla, niin kussakin iteraatiossa ratkaistava alitehtävä muuttuu lineaariseksi ohjelmointiongelmaksi .

Vaikka yleisen tapauksen pahimman tapauksen konvergenssiastetta ei voida parantaa, erityisongelmille, kuten tiukasti konveksille ongelmille, voidaan saavuttaa korkeammat konvergenssinopeudet [7] . $O(1/k)$

Ratkaisun ja primaali-duaalianalyysin arvon alarajat

Koska funktio on kupera , meillä on kahdelle pisteelle : $f$ $\mathbf {x} ,\mathbf {y} \in {\mathcal {D))$

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

Tämä pätee myös (tuntemattomaan) optimaaliseen ratkaisuun . Se on . Paras pisteen alaraja saadaan kaavasta $\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{tasattu))

Tämä viimeinen ongelma ratkaistaan jokaisessa Frank-Wulff-algoritmin iteraatiossa, joten i:nnen iteroinnin suunnan löytämisen aliongelman ratkaisua voidaan käyttää määrittämään kasvavat alarajat kussakin iteraatiossa antamalla ja ${\displaystyle \mathbf {s} _{k))$ $k$ ${\näyttötyyli 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}))

Tällaiset tuntemattoman optimiarvon alarajat ovat käytännössä erittäin tärkeitä, koska niitä voidaan käyttää algoritmin pysäyttämisen kriteerinä ja ne antavat tehokkaan indikaattorin approksimaation laadusta jokaisessa iteraatiossa, koska aina . $l_{k}\leqslant f(\mathbf {x} ^{*})\leqslant f(\mathbf {x} _{k})$

On osoitettu, että duaalisuusrako , joka on ero alarajan välillä , pienenee samalla nopeudella, ts. $f(\mathbf {x} _{k})$ ${\näyttötyyli l_{k))$ $f(\mathbf {x} _{k})-l_{k}=O(1/k).$

Muistiinpanot

↑ Algoritmin ovat kehittäneet Margarita Frank ja Philip Wolf, joten venäläisessä kirjallisuudessa laajalti käytetty nimi Frank-Wulf Algorithm on virheellinen.
↑ Levitin, Polyak, 1966 , s. 787-823.
↑ Frank ja Wolfe, 1956 , s. 95–110.
↑ Dunn ja Harshbarger 1978 , s. 432.
↑ Clarkson, 2010 , s. 1–30.
↑ Fukushima, 1984 , s. 169-177.
↑ Bertsekas, 1999 , s. 215.

Kirjallisuus

Levitin E.S., Polyak B.T. Minimointimenetelmät rajoitusten läsnä ollessa // Zh. Vychisl. matematiikka. ja matto. fysiikka - 1966. - V. 6 , no. 5 . - doi : 10.1016/0041-5553(66)90114-5 .
Frank M., Wolfe P. Algorithm for Quadratic Programming // Naval Research Logistics Quarterly. - 1956. - T. 3 , no. 1-2 . — S. 95–110 . - doi : 10.1002/nav.3800030109 .
Dunn JC, Harshbarger S. Ehdolliset gradienttialgoritmit avoimen silmukan askelkokosäännöillä // Journal of Mathematical Analysis and Applications. - 1978. - T. 62 , no. 2 . - S. 432 . - doi : 10.1016/0022-247X(78)90137-3 .
Clarkson KL Coresets, harva ahne approksimaatio ja Frank-Wolfe-algoritmi // ACM Transactions on Algorithms. - 2010. - T. 6 , no. 4 . - S. 1-30 . - doi : 10.1145/1824777.1824783 .
Modifioitu Frank-Wolfe-algoritmi liikenteen osoitusongelman ratkaisemiseksi // Liikennetutkimus Osa B: Metodologinen. - 1984. - T. 18 , no. 2 . - doi : 10.1016/0191-2615(84)90029-8 .
Dimitri Bertsekas. epälineaarinen ohjelmointi. - 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 , nro 1 . — S. 427–435 . (Katsausartikkeli)
Kuvaus Frank-Wulf-algoritmista
Jorge Nocedal, Stephen J. Wright. Numeerinen optimointi. – 2. - Berliini, New York: Springer-Verlag , 2006. - ISBN 978-0-387-30303-1 .
Fukushima, M. (1984). "Muutettu Frank-Wolfe-algoritmi liikenteen osoitusongelman ratkaisemiseksi." Liikennetutkimus Osa B: Metodologinen . 18 (2): 169-177. DOI : 10.1016/0191-2615(84)90029-8 .

Linkki

Marguerite Frank antaa henkilökohtaisen selostuksen algoritmin historiasta

Katso myös

Proksimaalinen gradienttimenetelmä

Optimointimenetelmät _
Yksiulotteinen	kultaisen leikkauksen menetelmä Dikotomia Paraabeli menetelmä Verkkohaku Yhtenäinen lohkohakumenetelmä Fibonaccin menetelmä Kolminkertainen haku Piyavsky menetelmä Vahva menetelmä
Nolla järjestys	Gaussin menetelmä Nelder-Meadin menetelmä Hook-Jeeves -menetelmä Rosenbrockin menetelmä Powellin menetelmä
Ensimmäinen tilaus	gradienttilasku Zeutendijk menetelmä Koordinaattilasku Konjugaattigradienttimenetelmä Kvasi-Newtonilaiset menetelmät Levenberg-Marquardt-algoritmi
toinen tilaus	Newtonin menetelmä Newton-Raphsonin menetelmä Broyden-Fletcher-Goldfarb-Shanno-algoritmi (BFGS)
Stokastinen	Monte Carlon menetelmä Simuloitu hehkutus Evoluutioalgoritmit differentiaalinen evoluutio Ant algoritmi Hiukkasparvimenetelmä Mehiläisyhdyskunnan algoritmi Satunnainen kävelymenetelmä
Lineaariset ohjelmointimenetelmät _	Yksinkertainen menetelmä Gomorin algoritmi Ellipsoidi menetelmä Potentiaalinen menetelmä
Epälineaariset ohjelmointimenetelmät	Jaksottainen neliöllinen ohjelmointi