Subgradient metode - Subgradient method

Subgradientmetoder er iterative metoder til løsning af konvekse minimeringsproblemer . Oprindeligt udviklet af Naum Z. Shor og andre i 1960'erne og 1970'erne, er subgradientmetoder konvergente, når de anvendes selv til en ikke-differentierbar objektiv funktion. Når den objektive funktion er differentierbar, bruger undergradientmetoder til ubegrænsede problemer den samme søgeretning som metoden med den stejleste nedstigning .

Subgradientmetoder er langsommere end Newtons metode, når den anvendes for at minimere to kontinuerligt differentierbare konvekse funktioner. Newtons metode konvergerer dog ikke på problemer, der har ikke-differentierbare kinks.

I de senere år er der blevet foreslået nogle indvendige punktmetoder til konvekse minimeringsproblemer, men subgradient projiceringsmetoder og relaterede bundtmetoder til afstamning forbliver konkurrencedygtige. Til konvekse minimeringsproblemer med meget stort antal dimensioner er subgradient-projiceringsmetoder egnede, fordi de kræver lidt opbevaring.

Fremskrivningsmetoder for undergradient anvendes ofte til store problemer med nedbrydningsteknikker. Sådanne nedbrydningsmetoder tillader ofte en simpel distribueret metode til et problem.

Klassiske undergradientregler

Lad være en konveks funktion med domæne . En klassisk undergradientmetode gentages ${\ displaystyle f: \ mathbb {R} ^ {n} \ til \ mathbb {R}}$${\ displaystyle \ mathbb {R} ^ {n}}$

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

hvor betegner enhver undergradient af at , og er iteratet af . Hvis der kan differentieres, er dens eneste undergradient selve gradientvektoren . Det kan ske, der ikke er en nedstigningsretning for kl . Vi opretholder derfor en liste, der holder styr på den hidtil laveste objektive funktionsværdi, dvs. ${\ displaystyle g ^ {(k)}}$ ${\ displaystyle f \}$${\ displaystyle x ^ {(k)} \}$${\ displaystyle x ^ {(k)}}$${\ displaystyle k ^ {th}}$${\ displaystyle x}$${\ displaystyle f \}$${\ displaystyle \ nabla f}$${\ displaystyle -g ^ {(k)}}$${\ displaystyle f \}$${\ displaystyle x ^ {(k)}}$${\ displaystyle f _ {\ rm {best}} \}$

${\ displaystyle f _ {\ rm {best}} ^ {(k)} = \ min \ {f _ {\ rm {best}} ^ {(k-1)}, f (x ^ {(k)}) \ }.}$

Trinstørrelsesregler

Mange forskellige typer trinstørrelsesregler bruges ved subgradientmetoder. Denne artikel noter fem regler klassisk trin-størrelse, for hvilken konvergenskriterierne beviser er kendt:

• Konstant trinstørrelse, ${\ displaystyle \ alpha _ {k} = \ alpha.}$
• Konstant trinlængde , hvilket giver ${\ displaystyle \ alpha _ {k} = \ gamma / \ lVert g ^ {(k)} \ rVert _ {2}}$${\ displaystyle \ lVert x ^ {(k + 1)} - x ^ {(k)} \ rVert _ {2} = \ gamma.}$
• Firkantet summerbart, men ikke summerbart trin, dvs. ethvert trin, der tilfredsstiller

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

• Ikke -ummable faldende, dvs. alle trinstørrelser, der er tilfredsstillende

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

• Ikke -ummable faldende trinlængder, dvs. hvor ${\ displaystyle \ alpha _ {k} = \ gamma _ {k} / \ lVert g ^ {(k)} \ rVert _ {2}}$

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

For alle fem regler bestemmes trinstørrelserne "off-line", før metoden gentages; trinstørrelserne afhænger ikke af forrige iterationer. Denne "off-line" egenskab ved subgradientmetoder adskiller sig fra de "on-line" trinstørrelsesregler, der anvendes til nedstigningsmetoder til differentierbare funktioner: Mange metoder til minimering af differentierbare funktioner tilfredsstiller Wolfes tilstrækkelige betingelser for konvergens, hvor trinstørrelser typisk afhænger af det aktuelle punkt og den aktuelle søgeretning. En omfattende diskussion af trinvise regler for undergradientmetoder, inklusive trinvise versioner, findes i bøgerne af Bertsekas og af Bertsekas, Nedic og Ozdaglar.

Konvergensresultater

For konstante trinlængde og skalerede subgradienter med euklidisk norm lig med en, konvergerer subgradientmetoden til en vilkårlig tæt tilnærmelse til minimumsværdien, dvs.

${\ displaystyle \ lim _ {k \ to \ infty} f _ {\ rm {best}} ^ {(k)} - f ^ {*} <\ epsilon}$ af et resultat af Shor .

Disse klassiske subgradientmetoder har dårlig ydeevne og anbefales ikke længere til generel brug. De bruges dog stadig bredt i specialiserede applikationer, fordi de er enkle, og de kan let tilpasses til at drage fordel af den særlige struktur af det aktuelle problem.

Undergradient-projektion & bundtmetoder

I løbet af 1970'erne foreslog Claude Lemaréchal og Phil Wolfe " bundtmetoder " af afstamning for problemer med konveks minimering. Betydningen af ​​udtrykket "bundtmetoder" har ændret sig betydeligt siden den tid. Moderne versioner og fuld konvergensanalyse blev leveret af Kiwiel. Moderne bundtmetoder bruger ofte " level control" -regler til valg af trinstørrelser og udvikler teknikker fra "subgradient-projection" -metoden fra Boris T. Polyak (1969). Der er dog problemer, som bundtmetoder giver ringe fordel i forhold til subgradient-projiceringsmetoder.

Begrænset optimering

Projiceret undergradient

En udvidelse af subgradientmetoden er den projicerede subgradientmetode , der løser det begrænsede optimeringsproblem

minimere genstand for ${\ displaystyle f (x) \}$

${\ displaystyle x \ i {\ mathcal {C}}}$

hvor er et konveks sæt . Den projicerede subgradientmetode bruger iteration ${\ displaystyle {\ mathcal {C}}}$

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

hvor er projektion på og er enhver undergradient af at ${\ displaystyle P}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle g ^ {(k)}}$${\ displaystyle f \}$${\ displaystyle x ^ {(k)}.}$

Generelle begrænsninger

Subgradientmetoden kan udvides til at løse problemet med begrænset ulighed

minimere genstand for ${\ displaystyle f_ {0} (x) \}$

${\ displaystyle f_ {i} (x) \ leq 0, \ quad i = 1, \ prikker, m}$

hvor er konvekse. Algoritmen har samme form som det ubegrænsede tilfælde ${\ displaystyle f_ {i}}$

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

hvor er en trinstørrelse, og er en undergradient af målet eller en af ​​begrænsningsfunktionerne i Take ${\ displaystyle \ alpha _ {k}> 0}$${\ displaystyle g ^ {(k)}}$${\ displaystyle x. \}$

${\ displaystyle g ^ {(k)} = {\ begin {cases} \ partial f_ {0} (x) & {\ text {if}} f_ {i} (x) \ leq 0 \; \ forall i = 1 \ prikker m \\\ delvis f_ {j} (x) & {\ tekst {for nogle}} j {\ tekst {sådan at}} f_ {j} (x)> 0 \ slut {cases}}}$

hvor betegner subdifferentialet af . Hvis det aktuelle punkt er muligt, bruger algoritmen en objektiv subgradient; hvis det aktuelle punkt er umuligt, vælger algoritmen en undergradient af enhver krænket begrænsning. ${\ displaystyle \ delvis f}$${\ displaystyle f \}$

Referencer

Yderligere læsning

• Bertsekas, Dimitri P. (1999). Ikke-lineær programmering . Belmont, MA: Athena Scientific. ISBN   1-886529-00-0 .
• Bertsekas, Dimitri P .; Nedic, Angelia; Ozdaglar, Asuman (2003). Konveks analyse og optimering (2. udgave). Belmont, MA: Athena Scientific. ISBN   1-886529-45-0 .
• Bertsekas, Dimitri P. (2015). Konvekse optimeringsalgoritmer . Belmont, MA: Athena Scientific. ISBN   978-1-886529-28-1 .
• Shor, Naum Z. (1985). Minimeringsmetoder til ikke-differentierbare funktioner . Springer-Verlag . ISBN   0-387-12763-1 .

• Ruszczyński, Andrzej (2006). Ikke-lineær optimering . Princeton, NJ: Princeton University Press . s. xii + 454. ISBN   978-0691119151 . MR   2199043 .

eksterne links

• EE364A og EE364B , Stanfords konvekse optimeringsforløb.