Undergradientmetoder

Subgradientmetoder er iterative metoder til at løse konvekse minimeringsproblemer . Subgradientmetoder udviklet af Naum Zuselevich Shor konvergerer, selv når de anvendes på ikke -differentierbare objektive funktioner . Når funktionen er differentierbar, bruger subgradientmetoder til ubegrænsede problemer den samme søgeretning som den stejleste nedstigningsmetode .

Subgradientmetoder er langsommere end Newtons metoder , hvor der bruges dobbelt kontinuerligt differentierbare konvekse funktioner til minimering. Newtons metoder holder dog op med at konvergere til problemer, der har ikke-differentierbare kinks.

I de senere år er nogle indre punktmetoder blevet foreslået til konvekse minimeringsproblemer, men både subgradientprojektionsmetoder og relaterede strålenedstigningsmetoder forbliver konkurrencedygtige. Til konvekse minimeringsproblemer med et stort antal dimensioner er subgradientprojektionsmetoder acceptable, fordi de kræver en lille mængde hukommelse.

Subgradientprojektionsmetoder anvendes ofte til problemer med store størrelser ved hjælp af nedbrydningsteknikker. Sådanne nedbrydningsmetoder giver ofte mulighed for en simpel distribueret opgavemetode.

Regler for den klassiske undergradient

Lade være en konveks funktion med domæne . Den klassiske subgradient-metode gentager sig $f:\mathbb {R} ^{n}\to \mathbb {R}$ $\mathbb {R} ^{n}$

{\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)))

hvor er enhver subdifferentiel af funktionen i punktet , og er den kth iteration af variablen . Hvis den kan differentieres, er dens eneste undergradient gradienten på . Det kan ske, at det ikke er en faldende retning for på punktet . Derfor indeholder vi en liste , som gemmer de fundne mindste værdier af den objektive funktion, dvs ${\displaystyle g^{(k)))$ $f$ $x^{{(k)}}$ $x^{{(k)}}$ $x$ $f\$ $\nabla f$ ${\displaystyle -g^{(k)))$ $f$ $x^{{(k)}}$ $f_{\rm {bedste))$

f_{\rm {bedste}}^{(k)}=\min\{f_{\rm {bedste}}^{(k-1)},f(x^{(k)})\ }.

Trinstørrelsesregler

Undergradientmetoder bruger et stort antal forskellige regler for valg af trinstørrelse. Her bemærker vi fem klassiske regler, for hvilke konvergensbeviser er kendt:

Konstant trinstørrelse ,. $\alpha _{k}=\alpha$
Konstant skridtlængde , hvilket giver . ${\displaystyle \alpha _{k}=\gamma /\lVert g^{(k)}\rVert _{2))$ $\lVert x^{(k+1)}-x^{(k)}\rVert _{2}=\gamma$
Kvadrat-summbar, men ikke-summbar trinstørrelse, dvs. enhver trinstørrelse for hvilken

\alpha _{k}\geqslant 0,\qquad \sum _{k=1}^{\infty }\alpha _{k}^{2}<\infty ,\qquad \sum _{k= 1}^{\infty }\alpha _{k}=\infty .

En ikke-summbar faldende trinstørrelse, det vil sige ethvert trin, der opfylder

\alpha _{k}\geqslant 0,\qquad \lim _{k\to \infty }\alpha _{k}=0,\qquad \sum _{k=1}^{\infty }\ alpha _{k}=\infty .

Ikke-summbar aftagende trinlængde, dvs. hvor ${\displaystyle \alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2))$

\gamma _{k}\geqslant 0,\qquad \lim _{k\to \infty }\gamma _{k}=0,\qquad \sum _{k=1}^{\infty }\ gamma _{k}=\infty .

For alle fem regler er trinstørrelsen bestemt "på forhånd", inden metoden starter. Trinstørrelsen er uafhængig af tidligere iterationer. Egenskaben "på forhånd" trinudvælgelse for subgradientmetoder adskiller sig fra de "igangværende" trinudvælgelsesregler, der bruges i metoder til differentierbare funktioner - mange metoder til at minimere differentiable funktioner opfylder Wolf-betingelserne for konvergens, hvor trinstørrelserne afhænger af den aktuelle punktets position og den aktuelle søgeretning. En omfattende diskussion af trinudvælgelsesreglerne for subgradientmetoder, herunder inkrementerende versioner, er givet i bogen af Bertsekas [1] og også i bogen af Bertsekas, Nedić og Ozdağlar [2] .

Konvergens

For en konstant trinlængde og skalerbare subgradienter med en euklidisk norm lig med én, nærmer subgradientmetoden sig vilkårligt tæt på minimumsværdien, dvs.

\lim _{k\to \infty }f_{\rm {bedste}}^{(k)}-f^{*}<\epsilon

ifølge Shore [3] .

Klassiske subgradientmetoder har dårlig konvergens og anbefales ikke længere til brug [4] [5] . De bruges dog stadig i specialiserede applikationer, fordi de er enkle og lette at tilpasse til specielle strukturer for at drage fordel af deres funktioner.

Subgradientprojektioner og strålemetoder

I løbet af 1970'erne foreslog Claude Lemérachel og Phil Wolf "skæremetoder" til nedstigning for konvekse minimeringsproblemer [6] . Betydningen af udtrykket "strålemetoder" har ændret sig meget siden da. Moderne versioner og en komplet konvergensanalyse blev givet af Kiel [7] . Moderne strålemetoder bruger ofte " niveaukontrol "-regler for valg af trinstørrelse, som udvikler teknikker fra "subgradientprojektion"-metoden af Boris T. Polyak (1969). Der er dog problemer, på grund af hvilke strålemetoder ofte giver ringe fordel i forhold til subgradientprojektionsmetoder [4] [5] .

Begrænset optimering

Subgradientprojektionsmetode

En udvidelse af subgradientmetoder er subgradientprojektionsmetoden , som løser det begrænsede optimeringsproblem

minimere under betingelsen

f(x)

x\in {\mathcal {C))

hvor er et konveks sæt . Subgradient-projektionsmetode bruger iterationer ${\mathcal {C}}$

x^{(k+1)}=P\venstre(x^{(k)}-\alpha _{k}g^{(k)}\right)

hvor er projektionen på , og er enhver undergradient ved . $P$ ${\mathcal {C}}$ ${\displaystyle g^{(k)))$ $f$ $x^{{(k)}}$

Generelle begrænsninger

Subgradientmetoden kan udvides til at løse problemet med begrænsninger i form af uligheder

minimere under betingelsen

f_{0}(x)

f_{i}(x)\leqslant 0,\quad i=1,\dots ,m

hvor funktionerne er konvekse. Algoritmen tager den samme form af sagen uden begrænsninger $f_{i}$

{\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)))

hvor er trinstørrelsen, og er undergradienten af målfunktionen eller en af begrænsningsfunktionerne i punktet . Her $\alpha _{k}>0$ ${\displaystyle g^{(k)))$ $x$

g^{(k)}={\begin{cases}\partial f_{0}(x)&f_{i}(x)\leqslant 0\;\forall i=1\dots m\\\partial f_{j}(x)&\eksisterer j:f_{j}(x)>0\end{cases}}

hvor betyder funktionens subdifferentiale . Hvis det aktuelle punkt er gyldigt, bruger algoritmen objektivfunktionen subgradient. Hvis punktet er ugyldigt, vælger algoritmen en undergradient af enhver begrænsning, der er overtrådt. $\partial f$ $f$

Noter

↑ Bertsekas, 2015 .
↑ Bertsekas, Nedic, Ozdaglar, 2003 .
↑ Konvergens af subgradientmetoder med konstant (skaleret) trin er angivet i øvelse 6.3.14(a) i Bertsekas ' bog (side 636) ( Bertsekas 1999 ), og han tilskriver dette resultat til Shor ( Shor 1985 )
↑ 1 2 Lemarechal, 2001 , s. 112-156.
↑ 1 2 Kiwiel, Larsson, Lindberg, 2007 , s. 669-686.
↑ Bertsekas, 1999 .
↑ Kiwiel, 1985 , s. 362.

Litteratur

Dimitri P. Bertsekas . Konvekse optimeringsalgoritmer. - Sekund. - Belmont, MA.: Athena Scientific, 2015. - ISBN 978-1-886529-28-1 .
Dimitri P. Bertsekas, Angelia Nedic, Asuman Ozdaglar. Konveks analyse og optimering. - Sekund. - Belmont, MA.: Athena Scientific, 2003. - ISBN 1-886529-45-0 .
Naum Z. Shor . Minimeringsmetoder for ikke-differentierbare funktioner. - Springer-Verlag , 1985. - ISBN 0-387-12763-1 .
Dimitri P. Bertsekas . ikke-lineær programmering. - Sekund. - Cambridge, MA.: Athena Scientific, 1999. - ISBN 1-886529-00-0 .
Krzysztof Kiwiel. Metoder til nedstigning til ikke-differentierbar optimering. - Berlin: Springer Verlag , 1985. - ISBN 978-3540156420 .
Claude Lemarechal. Lagrangian relaxation // Computational combinatorial optimization: Papers from the Spring School afholdt i Schloß Dagstuhl, 15.-19. maj 2000 / Michael Jünger, Denis Naddef. - Berlin: Springer-Verlag, 2001. - T. 2241. - (Lecture Notes in Computer Science). — ISBN 3-540-42877-1 . - doi : 10.1007/3-540-45586-8_4 .
Krzysztof C. Kiwiel, Torbjörn Larsson, Lindberg PO Lagrangiansk afslapning via ballstep subgradient-metoder // Mathematics of Operations Research. - 2007. - August ( bind 32 , nr. 3 ). — S. 669–686 . - doi : 10.1287/moor.1070.0261 .

Yderligere læsning

Andrzej Piotr Ruszczyński. ikke-lineær optimering. — Princeton, NJ: Princeton University Press , 2006. — s. xii+454. - ISBN 978-0691119151 .

Links

EE364A og EE364B , Stanfords konvekse optimeringsforløbssekvens.

Optimeringsmetoder _
Endimensionel	gyldne snit metode Modsætning Parabel metode Netsøgning Ensartet bloksøgningsmetode Fibonacci metode Ternær søgning Piyavsky metode Strongin metode
Nul orden	Gauss metode Nelder-Mead metode Hook-Jeeves metode Rosenbrock metode Powell metode
Første ordre	gradient nedstigning Zeutendijk metode Koordinat nedstigning Konjugeret gradientmetode Kvasi-newtonske metoder Levenberg-Marquardt algoritme
anden orden	Newtons metode Newton-Raphson metode Broyden-Fletcher-Goldfarb-Shanno-algoritme (BFGS)
Stokastisk	Monte Carlo metode Simuleret udglødning Evolutionære algoritmer differentiel evolution Myre-algoritme Partikelsværmmetode Algoritme for bikoloni Tilfældig gå-metode
Lineære programmeringsmetoder _	Enkel metode Gomoris algoritme Ellipsoid metode Potentiel metode
Ikke-lineære programmeringsmetoder	Sekventiel kvadratisk programmering