Proksymalna metoda gradientu - Proximal gradient method

Proksymalne metody gradientowe są uogólnioną formą rzutowania używaną do rozwiązywania nierozróżnialnych problemów wypukłych optymalizacji .

Wiele interesujących problemów można sformułować jako wypukłe problemy optymalizacji formy

${\ displaystyle \ operatorname {min} \ limity _ {x \ in \ mathbb {R} ^ {N}} \ sum _ {i = 1} ^ {n} f_ {i} (x)}$

gdzie są funkcje wypukłe zdefiniowane na podstawie których niektóre funkcje są nieróżniczkowalne. To wyklucza konwencjonalne techniki optymalizacji gładkich jak najbardziej stromego metodą opadania , sprzężoną metodą gradientu itp metody gradientu proksymalne może być używany. Metody te opierają się na podziale, w którym funkcje są używane indywidualnie, aby uzyskać łatwy do zaimplementowania algorytm. Nazywane są bliższa , ponieważ każdy non gładka funkcja u jest zaangażowany za pośrednictwem swojego operatora zbliżeniowej. Algorytm iteracyjnego progowania skurczu , rzutowany Landweber , rzutowany gradient, przemienne rzuty , metoda mnożników naprzemiennych kierunków , naprzemienny podział Bregman to szczególne przykłady algorytmów proksymalnych. Aby zapoznać się z teorią metod gradientu proksymalnego z perspektywy i z zastosowaniami do teorii uczenia się statystycznego , zobacz metody gradientu proksymalnego do uczenia się . ${\ displaystyle f_ {i}, \ i = 1, \ kropki, n}$${\ displaystyle f: \ mathbb {R} ^ {N} \ rightarrow \ mathbb {R}}$${\ displaystyle f_ {1}, ..., f_ {n}}$${\ displaystyle f_ {1}, ..., f_ {n}}$

Notacje i terminologia

Let The wymiarowa przestrzeni euklidesowej , być domeną funkcji . Załóżmy, że jest to niepusty, wypukły podzbiór . Następnie funkcję wskaźnika definiuje się jako ${\ displaystyle \ mathbb {R} ^ {N}}$${\ displaystyle N}$${\ Displaystyle f: \ mathbb {R} ^ {N} \ rightarrow (- \ infty, + \ infty]}$${\ displaystyle C}$${\ displaystyle \ mathbb {R} ^ {N}}$${\ displaystyle C}$

${\ displaystyle \ iota _ {C}: x \ mapsto {\ begin {przypadków} 0 i {\ text {if}} x \ in C \\ + \ infty & {\ text {if}} x \ notin C \ end {sprawy}}}$

${\ displaystyle p}$ -norm jest definiowany jako ( ) ${\ Displaystyle \ | \ cdot \ | _ {p}}$

${\ Displaystyle \ | x \ | _ {p} = (| x_ {1} | ^ {p} + | x_ {2} | ^ {p} + \ cdots + | x_ {N} | ^ {p}) ^ {1 / p}}$

Odległość od do jest definiowana jako ${\ Displaystyle x \ in \ mathbb {R} ^ {N}}$${\ displaystyle C}$

${\ Displaystyle D_ {C} (x) = \ min _ {y \ w C} \ | xy \ | _ {2}}$

Jeśli jest zamknięty i wypukły, rzut na to jedyny taki punkt . ${\ displaystyle C}$${\ Displaystyle x \ in \ mathbb {R} ^ {N}}$${\ displaystyle C}$${\ Displaystyle P_ {C} x \ w C}$${\ Displaystyle D_ {C} (x) = \ | x-P_ {C} x \ | _ {2}}$

Subdifferential od co jest dana przez ${\ displaystyle f}$${\ displaystyle x}$

${\ Displaystyle \ częściowe f (x) = \ {u \ in \ mathbb {R} ^ {N} \ mid \ forall y \ in \ mathbb {R} ^ {N}, (yx) ^ {\ mathrm {T }} u + f (x) \ leq f (y). \}}$

Projekcja na zestawy wypukłe (POCS)

Jednym z szeroko stosowanych algorytmów optymalizacji wypukłej jest rzutowanie na zbiory wypukłe (POCS). Algorytm ten służy do odzyskiwania / syntezy sygnału spełniającego jednocześnie kilka ograniczeń wypukłości. Niech będzie funkcją wskaźnikową niepustego zamkniętego zbioru wypukłego modelującego ograniczenie. Sprowadza się to do problemu wykonalności wypukłości, które wymaga od nas znalezienia takiego rozwiązania, które leży na przecięciu wszystkich zbiorów wypukłych . W metodzie POCS każdy zestaw jest włączany przez swój operator projekcji . Więc w każdej iteracji jest aktualizowana jako ${\ displaystyle f_ {i}}$${\ displaystyle C_ {i}}$${\ displaystyle C_ {i}}$${\ displaystyle C_ {i}}$ ${\ displaystyle P_ {C_ {i}}}$ ${\ displaystyle x}$

${\ Displaystyle x_ {k + 1} = P_ {C_ {1}} P_ {C_ {2}} \ cdots P_ {C_ {n}} x_ {k}}$

Jednak poza takimi problemami operatorzy projekcji nie są właściwi i bardziej ogólni operatorzy są zobowiązani do ich rozwiązania. Wśród różnych uogólnień pojęcia operatora projekcji wypukłej, które istnieją, operatory zbliżeniowe najlepiej nadają się do innych celów.

Definicja

Operatora zbliżeniowy wypukłego funkcji co jest definiowane jako unikalne rozwiązanie ${\ displaystyle f}$${\ displaystyle x}$

${\ Displaystyle \ nazwa operatora {argmin} \ limity _ {y} {\ bigg (} f (y) + {\ Frac {1} {2}} \ lewo \ | xy \ prawo \ | _ {2} ^ {2 } {\ bigg)}}$

i jest oznaczony . ${\ displaystyle \ operatorname {prox} _ {f} (x)}$

${\ displaystyle \ operatorname {prox} _ {f} (x): \ mathbb {R} ^ {N} \ rightarrow \ mathbb {R} ^ {N}}$

Zauważ, że w konkretnym przypadku, gdy jest funkcją wskaźnika jakiegoś zbioru wypukłego ${\ displaystyle f}$${\ displaystyle \ iota _ {C}}$${\ displaystyle C}$

${\ displaystyle {\ begin {wyrównane} \ operatorname {prox} _ {\ iota _ {C}} (x) & = \ operatorname {argmin} \ limits _ {y} {\ begin {przypadki} {\ Frac {1 } {2}} \ left \ | xy \ right \ | _ {2} ^ {2} & {\ text {if}} y \ in C \\ + \ infty & {\ text {if}} y \ notin C \ end {cases}} \\ & = \ operatorname {argmin} \ limits _ {y \ in C} {\ frac {1} {2}} \ left \ | xy \ right \ | _ {2} ^ { 2} \\ & = P_ {C} (x) \ end {aligned}}}$

pokazując, że operator bliskości jest rzeczywiście uogólnieniem operatora projekcji.

Operator bliskości z charakteryzuje się włączeniem ${\ displaystyle f}$

${\ displaystyle p = \ operatorname {prox} _ {f} (x) \ Leftrightarrow xp \ w \ częściowe f (p) \ qquad (\ forall (x, p) \ in \ mathbb {R} ^ {N} \ razy \ mathbb {R} ^ {N})}$

Jeśli jest różniczkowalna, to powyższe równanie sprowadza się do ${\ displaystyle f}$

${\ displaystyle p = \ operatorname {prox} _ {f} (x) \ Leftrightarrow xp = \ nabla f (p) \ quad (\ forall (x, p) \ in \ mathbb {R} ^ {N} \ razy \ mathbb {R} ^ {N})}$

Przykłady

Szczególnymi przypadkami Proksymalnych Metod Gradientu są

• Prognozowany Landweber
• Projekcja naprzemienna
• Metoda mnożników naprzemiennych

Zobacz też

• Projekcja naprzemienna
• Optymalizacja wypukła
• Algorytm Franka-Wolfe'a
• Operator proksymalny
• Proksymalne metody gradientu uczenia się

Uwagi

Bibliografia

• Rockafellar, RT (1970). Analiza wypukła . Princeton: Princeton University Press. CS1 maint: zniechęcony parametr ( link )
• Combettes, Patrick L .; Pesquet, Jean-Christophe (2011). Springer's Fixed Point Algorithms for Inverse Problems in Science and Engineering . 49 . s. 185–212.

Linki zewnętrzne

• Stephen Boyd i Lieven Vandenberghe Book, Optymalizacja wypukła
• EE364a: Convex Optimization I i EE364b: Convex Optimization II , strony główne kursu Stanforda
• EE227A: Lieven Vandenberghe Notes Wykład 18
• ProximalOperators.jl : pakiet Julia implementujący operatory proksymalne.
• ProximalAlgorithms.jl : pakiet Julii implementujący algorytmy oparte o operator proksymalny, w tym metodę gradientu proksymalnego.
• Repozytorium operatorów zbliżeniowych : zbiór operatorów zbliżeniowych zaimplementowanych w Matlabie i Pythonie .