Metoda podgradientowa - Subgradient method

Metody subgradientowe to iteracyjne metody rozwiązywania problemów minimalizacji wypukłości . Pierwotnie opracowane przez Nauma Z. Shora i innych w latach sześćdziesiątych i siedemdziesiątych XX wieku metody subgradientowe są zbieżne, gdy są stosowane nawet do nieróżniczkowalnej funkcji celu. Gdy funkcja celu jest różniczkowalna, metody podgradientowe dla problemów nieograniczonych wykorzystują ten sam kierunek poszukiwań, co metoda najbardziej stromego spadku .

Metody subgradientowe są wolniejsze niż metoda Newtona, gdy są stosowane w celu zminimalizowania dwukrotnie różniczkowalnych wypukłych funkcji w sposób ciągły. Jednak metoda Newtona nie jest zbieżna w przypadku problemów, które mają nierozróżnialne załamania.

W ostatnich latach zaproponowano pewne metody punktu wewnętrznego w celu rozwiązania problemów z minimalizacją wypukłości, ale metody projekcji subgradientowej i powiązane metody opadania wiązek pozostają konkurencyjne. W przypadku problemów z minimalizacją wypukłości przy bardzo dużej liczbie wymiarów odpowiednie są metody rzutowania subgradientowego, ponieważ wymagają one niewielkiego przechowywania.

Metody rzutowania subgradientowego są często stosowane w przypadku wielkoskalowych problemów z technikami dekompozycji. Takie metody dekompozycji często pozwalają na prostą metodę rozproszoną dla problemu.

Klasyczne reguły subgradientowe

Niech będzie funkcją wypukłą z dziedziną . Klasyczna metoda subgradientowa iteruje ${\ Displaystyle f: \ mathbb {R} ^ {n} \ do \ mathbb {R}}$${\ displaystyle \ mathbb {R} ^ {n}}$

${\ Displaystyle x ^ {(k + 1)} = x ^ {(k)} - \ alfa _ {k} g ^ {(k)} \}$

gdzie oznacza dowolny subgradient się na i jest iteracyjne z . Jeśli jest różniczkowalna, to jej jedynym subgradientem jest sam wektor gradientu . Może się zdarzyć, że nie jest to kierunek zejścia o godz . Dlatego prowadzimy listę, która śledzi najniższą znalezioną dotychczas wartość funkcji celu, tj ${\ 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 {najlepiej}} ^ {(k)} = \ min \ {f _ {\ rm {najlepiej}} ^ {(k-1)}, f (x ^ {(k)}) \ }.}$

Zasady dotyczące wielkości stopni

Metody subgradientowe wykorzystują wiele różnych typów reguł wielkości kroku. W tym artykule opisano pięć klasycznych reguł wielkości kroku, dla których znane są dowody zbieżności :

• Stały rozmiar kroku, ${\ displaystyle \ alpha _ {k} = \ alpha.}$
• Stała długość kroku , co daje ${\ Displaystyle \ alpha _ {k} = \ gamma / \ lVert g ^ {(k)} \ rVert _ {2}}$${\ Displaystyle \ lVert x ^ {(k + 1)} - x ^ {(k)} \ rVert _ {2} = \ gamma.}$
• Kwadratowy, ale nie dający się zsumować rozmiar kroku, tj. Zadowalające rozmiary stopni

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

• Niemożliwe zmniejszanie, tj. Zadowalające rozmiary stopni

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

• Niemożliwe do zwiększenia malejące długości kroku, tj. Gdzie ${\ 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.}$

Dla wszystkich pięciu reguł rozmiary kroków są określane „off-line”, przed iteracją metody; rozmiary stopni nie zależą od poprzedzających iteracji. Ta właściwość „off-line” metod subgradientowych różni się od reguł wielkości kroku „on-line” stosowanych w metodach zejścia dla funkcji różniczkowalnych: Wiele metod minimalizacji funkcji różniczkowalnych spełnia warunki dostateczne dla zbieżności Wolfe'a, gdzie rozmiary kroku zwykle zależą od aktualny punkt i aktualny kierunek wyszukiwania. Obszerne omówienie reguł stopniowania dla metod subgradientowych, w tym wersji przyrostowych, znajduje się w książkach Bertsekasa oraz Bertsekasa, Nedica i Ozdaglara.

Wyniki konwergencji

Dla stałej długości kroku i skalowanych subgradientów o normie euklidesowej równej jeden, metoda subgradientów jest zbieżna do arbitralnie bliskiego przybliżenia do wartości minimalnej, to znaczy

${\ displaystyle \ lim _ {k \ to \ infty} f _ {\ rm {najlepiej}} ^ {(k)} - f ^ {*} <\ epsilon}$ przez wynik Shor .

Te klasyczne metody subgradientowe mają słabą wydajność i nie są już zalecane do ogólnego użytku. Jednak nadal są szeroko stosowane w wyspecjalizowanych aplikacjach, ponieważ są proste i można je łatwo dostosować, aby wykorzystać specjalną strukturę danego problemu.

Metody rzutowania subgradientowego i pakietów

W latach siedemdziesiątych Claude Lemaréchal i Phil Wolfe zaproponowali „wiązkowe metody” zejścia dla problemów minimalizacji wypukłości. Od tego czasu znaczenie terminu „metody pakietowe” uległo znaczącej zmianie. Nowoczesne wersje i pełną analizę zbieżności dostarczył Kiwiel. Współczesne metody wiązek często wykorzystują reguły „kontroli poziomu ” do wybierania wielkości stopni, rozwijając techniki z metody „subgradient-projection” Borisa T. Polyaka (1969). Istnieją jednak problemy, w przypadku których metody wiązkowe mają niewielką przewagę nad metodami rzutowania subgradientowego.

Ograniczona optymalizacja

Przewidywany subgradient

Jednym z rozszerzeń metody subgradientowej jest metoda subgradientów rzutowanych , która rozwiązuje problem optymalizacji z ograniczeniami

zminimalizować temat ${\ Displaystyle f (x) \}$

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

gdzie jest wypukły zbiór . Metoda prognozowanych podgradientów wykorzystuje iterację ${\ displaystyle {\ mathcal {C}}}$

${\ Displaystyle x ^ {(k + 1)} = P \ lewo (x ^ {(k)} - \ alfa _ {k} g ^ {(k)} \ prawej)}$

gdzie jest projekcja na i jest dowolnym podgradientem at ${\ displaystyle P}$${\ displaystyle {\ mathcal {C}}}$${\ Displaystyle g ^ {(k)}}$${\ displaystyle f \}$${\ Displaystyle x ^ {(k)}.}$

Ogólne ograniczenia

Metodę subgradientową można rozszerzyć w celu rozwiązania problemu ograniczonego nierównościami

zminimalizować temat ${\ displaystyle f_ {0} (x) \}$

${\ displaystyle f_ {i} (x) \ równoważnik 0, \ quad i = 1, \ kropki, m}$

gdzie są wypukłe. Algorytm ma taką samą postać jak przypadek nieograniczony ${\ displaystyle f_ {i}}$

${\ Displaystyle x ^ {(k + 1)} = x ^ {(k)} - \ alfa _ {k} g ^ {(k)} \}$

gdzie jest wielkością kroku i jest subgradientem celu lub jednej z funkcji ograniczających w Take ${\ displaystyle \ alpha _ {k}> 0}$${\ Displaystyle g ^ {(k)}}$${\ Displaystyle x. \}$

${\ Displaystyle g ^ {(k)} = {\ rozpocząć {przypadków} \ częściowe f_ {0} (x) & {\ tekst {if}} f_ {i} (x) \ równoważnik 0 \; \ forall i = 1 \ dots m \\\ częściowe f_ {j} (x) & {\ text {dla niektórych}} j {\ text {takie, że}} f_ {j} (x)> 0 \ end {przypadki}}}$

gdzie oznacza subdifferential się . Jeśli aktualny punkt jest wykonalny, algorytm używa obiektywnego podgradienta; jeśli bieżący punkt jest niewykonalny, algorytm wybiera podgradient dowolnego naruszonego ograniczenia. ${\ Displaystyle \ częściowe f}$${\ displaystyle f \}$

Bibliografia

Dalsza lektura

• Bertsekas, Dimitri P. (1999). Programowanie nieliniowe . Mgr Belmont: Athena Scientific. ISBN   1-886529-00-0 .
• Bertsekas, Dimitri P .; Nedic, Angelia; Ozdaglar, Asuman (2003). Analiza wypukła i optymalizacja (wydanie drugie). Mgr Belmont: Athena Scientific. ISBN   1-886529-45-0 .
• Bertsekas, Dimitri P. (2015). Algorytmy optymalizacji wypukłości . Mgr Belmont: Athena Scientific. ISBN   978-1-886529-28-1 .
• Shor, Naum Z. (1985). Metody minimalizacji funkcji nieróżniczkowalnych . Springer-Verlag . ISBN   0-387-12763-1 .

• Ruszczyński, Andrzej (2006). Optymalizacja nieliniowa . Princeton, NJ: Princeton University Press . s. xii + 454. ISBN   978-0691119151 . MR   2199043 .

Linki zewnętrzne

• EE364A i EE364B , sekwencja kursu optymalizacji wypukłej Stanforda.