Subgradientmetoder

Subgradientmetoder är iterativa metoder för att lösa konvexa minimeringsproblem . Subgradientmetoder utvecklade av Naum Zuselevich Shor konvergerar även när de tillämpas på icke -differentiera objektiva funktioner . När funktionen är differentierbar använder subgradientmetoder för obegränsade problem samma sökriktning som den brantaste nedstigningsmetoden .

Subgradientmetoder är långsammare än Newtons metoder , där dubbelt kontinuerligt differentierbara konvexa funktioner används för minimering. Newtons metoder upphör dock att konvergera till problem som har icke-differentierbara kinks.

Under de senaste åren har vissa inre punktmetoder föreslagits för konvexa minimeringsproblem, men både subgradientprojektionsmetoder och relaterade strålnedstigningsmetoder förblir konkurrenskraftiga. För konvexa minimeringsproblem med ett stort antal dimensioner är subgradientprojektionsmetoder acceptabla eftersom de kräver en liten mängd minne.

Subgradientprojektionsmetoder tillämpas ofta på problem med stor storlek med hjälp av nedbrytningstekniker. Sådana nedbrytningsmetoder tillåter ofta en enkel distribuerad uppgiftsmetod.

Regler för den klassiska subgradienten

Låta vara en konvex funktion med domän . Den klassiska subgradientmetoden upprepas $f:\mathbb {R} ^{n}\to \mathbb {R}$ $\mathbb {R} ^{n}$

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

där är någon subdifferential för funktionen vid punkten , och är den k: te iterationen av variabeln . Om den är differentierbar är dess enda undergradient gradienten på . Det kan hända att det inte är en minskande riktning för vid punkten . Därför innehåller vi en lista , som lagrar de hittade minsta värdena för objektivfunktionen, det vill säga ${\displaystyle g^{(k)))$ $f$ $x^{{(k)}}$ $x^{{(k)}}$ $x$ $f\$ $\nabla f$ ${\displaystyle -g^{(k)))$ $f$ $x^{{(k)}}$ $f_{\rm {bästa))$

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

Stegstorleksregler

Undergradientmetoder använder ett stort antal olika regler för val av stegstorlek. Här noterar vi fem klassiska regler för vilka konvergensbevis är kända:

Konstant stegstorlek, . $\alpha _{k}=\alpha$
Konstant steglängd vilket ger . ${\displaystyle \alpha _{k}=\gamma /\lVert g^{(k)}\rVert _{2))$ $\lVert x^{(k+1)}-x^{(k)}\rVert _{2}=\gamma$
Kvadratisk summerbar men icke summerbar stegstorlek, d.v.s. valfri stegstorlek för vilken

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

En icke summerbar minskande stegstorlek, det vill säga vilket steg som helst som uppfyller

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

Ej summerbar minskande steglängd, d.v.s. var ${\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 .

För alla fem reglerna bestäms stegstorleken "i förväg", innan metoden startar. Stegstorleken är oberoende av tidigare iterationer. Stegvalsegenskapen "i förväg" för subgradientmetoder skiljer sig från de "pågående" stegvalsreglerna som används i metoder för differentierbara funktioner - många metoder för att minimera differentierbara funktioner uppfyller Wolf-villkoren för konvergens, där stegstorlekarna beror på den aktuella punktens position och den aktuella sökriktningen. En omfattande diskussion av stegvalsreglerna för subgradientmetoder, inklusive inkrementerande versioner, ges i boken av Bertsekas [1] och även i boken av Bertsekas, Nedić och Ozdağlar [2] .

Konvergens

För en konstant steglängd och skalbara subgradienter med en euklidisk norm lika med ett, närmar sig subgradientmetoden godtyckligt minimivärdet, dvs.

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

enligt Shore [3] .

Klassiska subgradientmetoder har dålig konvergens och rekommenderas inte längre för användning [4] [5] . Men de används fortfarande i specialiserade applikationer eftersom de är enkla och lätta att anpassa till speciella strukturer för att dra nytta av deras egenskaper.

Subgradientprojektioner och strålmetoder

Under 1970-talet föreslog Claude Lemérachel och Phil Wolf "kärvemetoder" för nedstigning för konvexa minimeringsproblem [6] . Innebörden av begreppet "strålemetoder" har förändrats mycket sedan dess. Moderna versioner och en fullständig konvergensanalys gavs av Kiel [7] . Moderna strålmetoder använder ofta " nivåkontroll "-regler för val av stegstorlek, som utvecklar tekniker från metoden "subgradientprojektion" av Boris T. Polyak (1969). Det finns dock problem på grund av vilka strålmetoder ofta ger liten fördel jämfört med subgradientprojektionsmetoder [4] [5] .

Begränsad optimering

Subgradientprojektionsmetod

En förlängning av subgradientmetoder är subgradientprojektionsmetoden , som löser det begränsade optimeringsproblemet

minimera under villkoret

f(x)

x\in {\mathcal {C))

var är en konvex uppsättning . Subgradientprojektionsmetod använder iterationer ${\mathcal {C}}$

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

var är projektionen på och är någon undergradient vid . $P$ ${\mathcal {C}}$ ${\displaystyle g^{(k)))$ $f$ $x^{{(k)}}$

Allmänna begränsningar

Subgradientmetoden kan utökas för att lösa problemet med begränsningar i form av ojämlikheter

minimera under villkoret

f_{0}(x)

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

där funktionerna är konvexa. Algoritmen har samma form av fallet utan begränsningar $f_{i}$

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

var är stegstorleken och är undergradienten för målfunktionen eller en av begränsningsfunktionerna vid punkten . Här $\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)&\exists j:f_{j}(x)>0\end{cases}}

där betyder funktionens subdifferential . Om den aktuella punkten är giltig använder algoritmen subgradienten för objektivfunktionen. Om punkten är ogiltig väljer algoritmen en undergradient av alla begränsningar som överträds. $\partial f$ $f$

Anteckningar

↑ Bertsekas, 2015 .
↑ Bertsekas, Nedic, Ozdaglar, 2003 .
↑ Konvergens av subgradientmetoder med konstant (skalad) steg anges i övning 6.3.14(a) i Bertsekas bok (sida 636) ( Bertsekas 1999 ) och han tillskriver detta resultat till Shor ( Shor 1985 )
↑ 1 2 Lemarechal, 2001 , sid. 112–156.
↑ 1 2 Kiwiel, Larsson, Lindberg, 2007 , sid. 669–686.
↑ Bertsekas, 1999 .
↑ Kiwiel, 1985 , sid. 362.

Litteratur

Dimitri P. Bertsekas . Konvexa optimeringsalgoritmer. — För det andra. - Belmont, MA.: Athena Scientific, 2015. - ISBN 978-1-886529-28-1 .
Dimitri P. Bertsekas, Angelia Nedic, Asuman Ozdaglar. Konvex analys och optimering. — För det andra. - Belmont, MA.: Athena Scientific, 2003. - ISBN 1-886529-45-0 .
Naum Z. Shor . Minimeringsmetoder för icke-differentiera funktioner. - Springer-Verlag , 1985. - ISBN 0-387-12763-1 .
Dimitri P. Bertsekas . icke-linjär programmering. — För det andra. - Cambridge, MA: Athena Scientific, 1999. - ISBN 1-886529-00-0 .
Krzysztof Kiwiel. Nedstigningsmetoder för icke-differentierbar optimering. - Berlin: Springer Verlag , 1985. - ISBN 978-3540156420 .
Claude Lemarechal. Lagrangian relaxation // Computational combinatorial optimization: Papers from the Spring School som hölls 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 Lagrangian relaxation via ballstep subgradient methods // Mathematics of Operations Research. - 2007. - Augusti ( vol. 32 , nr 3 ). — S. 669–686 . - doi : 10.1287/moor.1070.0261 .

Ytterligare läsning

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

Länkar

EE364A och EE364B , Stanfords konvexa optimeringskurssekvens.

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