Subgradientní metoda - Subgradient method - Wikipedia

Subgradientní metody jsou iterační metody k řešení konvexní minimalizace problémy. Původně vyvinutý Naum Z. Shor a další v šedesátých a sedmdesátých letech jsou metody subgradientu konvergentní, pokud jsou aplikovány i na nediferencovatelnou objektivní funkci. Když je objektivní funkce diferencovatelná, sub-gradientní metody pro neomezené problémy používají stejný směr hledání jako metoda nejstrmější sestup.

Subgradientní metody jsou při použití pomalejší než Newtonova metoda, aby se minimalizovaly dvakrát kontinuálně diferencovatelné konvexní funkce. Newtonova metoda však nedokáže konvergovat na problémy, které mají nediferencovatelné smyčky.

V posledních letech některé metody vnitřních bodů byly navrženy pro konvexní problémy s minimalizací, ale metody podstupňového promítání a související svazkové metody sestupu zůstávají konkurenceschopné. Pro konvexní problémy s minimalizací s velkým počtem dimenzí jsou vhodné metody subgradient-projection, protože vyžadují malé úložiště.

Metody subgradientní projekce se často používají na rozsáhlé problémy s technikami rozkladu. Takové metody rozkladu často umožňují jednoduchou distribuovanou metodu řešení problému.

Klasická pravidla přechodu

Nechat ${ displaystyle f: mathbb {R} ^ {n} to mathbb {R}}$ být konvexní funkce s doménou ${ displaystyle mathbb {R} ^ {n}}$ . Klasická subgradientní metoda iteruje

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

kde ${ displaystyle g ^ {(k)}}$ označuje je žádný subgradient z ${ displaystyle f }$ na ${ displaystyle x ^ {(k)} }$ , a ${ displaystyle x ^ {(k)}}$ je ${ displaystyle k ^ {th}}$ opakovat ${ displaystyle x}$ . Li ${ displaystyle f }$ je diferencovatelný, pak jeho jediným subgradientem je vektor přechodu ${ displaystyle nabla f}$ může se to stát ${ displaystyle -g ^ {(k)}}$ není směr sestupu pro ${ displaystyle f }$ na ${ displaystyle x ^ {(k)}}$ . Proto vedeme seznam ${ displaystyle f _ { rm {nejlepší}} }$ který sleduje dosud nalezenou nejnižší hodnotu objektivní funkce, tj.

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

Pravidla velikosti kroku

Metody subgradientu používají mnoho různých typů pravidel velikosti kroku. Tento článek uvádí pět klasických pravidel velikosti kroku, pro které konvergence důkazy jsou známy:

Konstantní velikost kroku, ${ displaystyle alpha _ {k} = alfa.}$
Konstantní délka kroku, ${ displaystyle alpha _ {k} = gamma / lVert g ^ {(k)} rVert _ {2}}$ , což dává ${ displaystyle lVert x ^ {(k + 1)} - x ^ {(k)} rVert _ {2} = gama.}$
Čtvercová sumarizovatelná, ale ne sumarizovatelná velikost kroku, tj. Uspokojivé jakékoli velikosti kroku

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

Nesmrtelné zmenšování, tj. Uspokojivé jakékoli velikosti kroku

{ displaystyle alpha _ {k} geq 0, qquad lim _ {k to infty} alpha _ {k} = 0, qquad suma _ {k = 1} ^ { infty} alpha _ {k} = infty.}

Nesmrtelné zmenšující se délky kroků, tj. ${ displaystyle alpha _ {k} = gamma _ {k} / lVert g ^ {(k)} rVert _ {2}}$ , kde

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

U všech pěti pravidel jsou velikosti kroků určeny „off-line“ před iterací metody; velikosti kroků nezávisí na předchozích iteracích. Tato „off-line“ vlastnost subgradientních metod se liší od „on-line“ pravidel velikosti kroku používaných pro metody sestupu pro diferencovatelné funkce: Mnoho metod pro minimalizaci diferencovatelných funkcí uspokojuje Wolfeho dostatečné podmínky pro konvergenci, kde velikost kroku obvykle závisí na aktuální bod a aktuální směr hledání. Rozsáhlá diskuse o pravidlech postupnosti pro metody subgradientu, včetně přírůstkových verzí, je uvedena v knihách Bertsekase^[1]a Bertsekas, Nedic a Ozdaglar. ^[2]

Výsledky konvergence

Pro konstantní délku kroku a zmenšené podskupiny Euklidovská norma rovno jedné, metoda subgradientu konverguje na libovolně blízkou aproximaci minimální hodnoty, tj

{ displaystyle lim _ {k to infty} f _ { rm {best}} ^ {(k)} - f ^ {*} < epsilon}

výsledkem Shor.^[3]

Tyto klasické metody subgradientu mají špatný výkon a již se nedoporučují pro obecné použití.^[4]^[5] Ve specializovaných aplikacích se však stále široce používají, protože jsou jednoduché a lze je snadno upravit, aby využily výhody speciální struktury daného problému.

Subgradient-projection & bundle methods

V 70. letech Claude Lemaréchal a Phil Wolfe navrhli „svazkové metody“ původu pro problémy s konvexní minimalizací.^[6] Význam pojmu „metody svazků“ se od té doby významně změnil. Moderní verze a úplnou konvergenční analýzu poskytl Kiwiel.^[7] Současné metody svazků často používají „úroveň kontrolní "pravidla pro výběr velikosti kroků, vývoj technik z metody„ subgradient-projection "Borise T. Polyaka (1969). Existují však problémy, u nichž metody svazků nabízejí malou výhodu oproti metodám subgradient-projection.^[4]^[5]

Omezená optimalizace

Předpokládaný podstupeň

Jedním rozšířením metody subgradientu je projektovaná subgradientní metoda, který řeší omezený optimalizační problém

minimalizovat

{ displaystyle f (x) }

podléhá

{ displaystyle x in { mathcal {C}}}

kde ${ displaystyle { mathcal {C}}}$ je konvexní sada. Metoda projektovaného subgradientu používá iteraci

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

kde ${ displaystyle P}$ je projekce zapnuta ${ displaystyle { mathcal {C}}}$ a ${ displaystyle g ^ {(k)}}$ je jakýkoli podskupina ${ displaystyle f }$ na ${ displaystyle x ^ {(k)}.}$

Obecná omezení

Metodu subgradient lze rozšířit tak, aby vyřešila problém omezený nerovností

minimalizovat

{ displaystyle f_ {0} (x) }

podléhá

{ displaystyle f_ {i} (x) leq 0, quad i = 1, tečky, m}

kde ${ displaystyle f_ {i}}$ jsou konvexní. Algoritmus má stejnou formu jako neomezený případ

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

kde ${ displaystyle alpha _ {k}> 0}$ je velikost kroku a ${ displaystyle g ^ {(k)}}$ je podskupina cíle nebo jedné z omezujících funkcí v ${ displaystyle x. }$ Vzít

{ displaystyle g ^ {(k)} = { začátek {případů} částečný f_ {0} (x) & { text {if}} f_ {i} (x) leq 0 ; forall i = 1 dots m částečné f_ {j} (x) & { text {pro některé}} j { text {takový že}} f_ {j} (x)> 0 end {případy}}}

kde ${ displaystyle částečné f}$ označuje subdiferenciální z ${ displaystyle f }$ . Pokud je aktuální bod proveditelný, použije algoritmus objektivní podgradient; pokud je aktuální bod neproveditelný, zvolí algoritmus subgradient jakéhokoli porušeného omezení.

Reference

^ Bertsekas, Dimitri P. (2015). Konvexní optimalizační algoritmy (Druhé vydání.). Belmont, MA .: Athena Scientific. ISBN 978-1-886529-28-1.
^ Bertsekas, Dimitri P .; Nedic, Angelia; Ozdaglar, Asuman (2003). Konvexní analýza a optimalizace (Druhé vydání.). Belmont, MA .: Athena Scientific. ISBN 1-886529-45-0.
^ Přibližná konvergence subgradientní metody konstantní velikosti (škálované) stupně je uvedena jako cvičení 6.3.14 (a) v Bertsekas (strana 636): Bertsekas, Dimitri P. (1999). Nelineární programování (Druhé vydání.). Cambridge, MA .: Athena Scientific. ISBN 1-886529-00-0. Na stránce 636 Bertsekas připisuje tento výsledek Shorovi: Shor, Naum Z. (1985). Metody minimalizace pro nediferencovatelné funkce. Springer-Verlag. ISBN 0-387-12763-1.
^ ^A ^b Lemaréchal, Claude (2001). "Lagrangeova relaxace". V Michael Jünger a Denis Naddef (ed.). Výpočetní kombinatorická optimalizace: Příspěvky z jarní školy konané ve Schloß Dagstuhl, 15. – 19. Května 2000. Přednášky z informatiky. 2241. Berlín: Springer-Verlag. str. 112–156. doi:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. PAN 1900016.CS1 maint: ref = harv (odkaz)
^ ^A ^b Kiwiel, Krzysztof C .; Larsson, Torbjörn; Lindberg, P. O. (srpen 2007). „Lagrangeova relaxace pomocí kuličkových subgradientních metod“. Matematika operačního výzkumu. 32 (3): 669–686. doi:10,1287 / měsíc 1070,0261. PAN 2348241.CS1 maint: ref = harv (odkaz)
^ Bertsekas, Dimitri P. (1999). Nelineární programování (Druhé vydání.). Cambridge, MA .: Athena Scientific. ISBN 1-886529-00-0.
^ Kiwiel, Krzysztof (1985). Metody sestupu pro nediferencovatelnou optimalizaci. Berlín: Springer Verlag. str. 362. ISBN 978-3540156420. PAN 0797754.

Další čtení

Bertsekas, Dimitri P. (1999). Nelineární programování. Belmont, MA .: Athena Scientific. ISBN 1-886529-00-0.
Bertsekas, Dimitri P .; Nedic, Angelia; Ozdaglar, Asuman (2003). Konvexní analýza a optimalizace (Druhé vydání.). Belmont, MA .: Athena Scientific. ISBN 1-886529-45-0.
Bertsekas, Dimitri P. (2015). Konvexní optimalizační algoritmy. Belmont, MA .: Athena Scientific. ISBN 978-1-886529-28-1.
Shor, Naum Z. (1985). Metody minimalizace pro nediferencovatelné funkce. Springer-Verlag. ISBN 0-387-12763-1.

Ruszczyński, Andrzej (2006). Nelineární optimalizace. Princeton, NJ: Princeton University Press. str. xii + 454. ISBN 978-0691119151. PAN 2199043.

externí odkazy

EE364A a EE364B, Sled konvexní optimalizace kurzu Stanfordu.

[1] Bertsekas, Dimitri P. (2015). Konvexní optimalizační algoritmy (Druhé vydání.). Belmont, MA .: Athena Scientific. ISBN 978-1-886529-28-1.

[2] Bertsekas, Dimitri P .; Nedic, Angelia; Ozdaglar, Asuman (2003). Konvexní analýza a optimalizace (Druhé vydání.). Belmont, MA .: Athena Scientific. ISBN 1-886529-45-0.

[3] Přibližná konvergence subgradientní metody konstantní velikosti (škálované) stupně je uvedena jako cvičení 6.3.14 (a) v Bertsekas (strana 636): Bertsekas, Dimitri P. (1999). Nelineární programování (Druhé vydání.). Cambridge, MA .: Athena Scientific. ISBN 1-886529-00-0. Na stránce 636 Bertsekas připisuje tento výsledek Shorovi: Shor, Naum Z. (1985). Metody minimalizace pro nediferencovatelné funkce. Springer-Verlag. ISBN 0-387-12763-1.

[Lem-4] A ^b Lemaréchal, Claude (2001). "Lagrangeova relaxace". V Michael Jünger a Denis Naddef (ed.). Výpočetní kombinatorická optimalizace: Příspěvky z jarní školy konané ve Schloß Dagstuhl, 15. – 19. Května 2000. Přednášky z informatiky. 2241. Berlín: Springer-Verlag. str. 112–156. doi:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. PAN 1900016.CS1 maint: ref = harv (odkaz)

[KLL-5] A ^b Kiwiel, Krzysztof C .; Larsson, Torbjörn; Lindberg, P. O. (srpen 2007). „Lagrangeova relaxace pomocí kuličkových subgradientních metod“. Matematika operačního výzkumu. 32 (3): 669–686. doi:10,1287 / měsíc 1070,0261. PAN 2348241.CS1 maint: ref = harv (odkaz)

[6] Bertsekas, Dimitri P. (1999). Nelineární programování (Druhé vydání.). Cambridge, MA .: Athena Scientific. ISBN 1-886529-00-0.

[7] Kiwiel, Krzysztof (1985). Metody sestupu pro nediferencovatelnou optimalizaci. Berlín: Springer Verlag. str. 362. ISBN 978-3540156420. PAN 0797754.

[1]

[2]

[3]

[4]

[5]

[6]

[7]