Metoda proximálního gradientu - Proximal gradient method

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (listopad 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Metody proximálního gradientu jsou zobecněná forma projekce používaná k řešení nediferencovatelnosti konvexní optimalizace problémy.

Mnoho zajímavých problémů lze formulovat jako konvexní optimalizační problémy formy:

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

kde ${ displaystyle f_ {i}, i = 1, tečky, n}$ jsou konvexní funkce definováno od ${ displaystyle f: mathbb {R} ^ {N} rightarrow mathbb {R}}$pokud jsou některé funkce nediferencovatelné, vylučuje to naše běžné techniky hladké optimalizace, jako jeMetoda nejstrmějšího sestupu, metoda konjugovaného gradientu Místo toho lze použít metody proximálního gradientu. Tyto metody pokračují rozdělením funkcí ${ displaystyle f_ {1}, ..., f_ {n}}$ se používají jednotlivě, aby se snadno získal implementovatelný algoritmus. Nazývají se proximální protože každý ne plynulá funkce mezi ${ displaystyle f_ {1}, ..., f_ {n}}$ je zapojen prostřednictvím svého operátora přiblížení. Alterativní algoritmus prahování iterativního smrštění,^[1] projektovaný Landweber, projektovaný přechod, střídavé projekce, metoda střídavého směru multiplikátorů, alterningsplit Bregman jsou speciální instance proximálních algoritmů.^[2] Pro teorii metod proximálního gradientu z pohledu as aplikacemi do statistická teorie učení viz metody proximálního gradientu pro učení.

Zápisy a terminologie

Nechat ${ displaystyle mathbb {R} ^ {N}}$, ${ displaystyle N}$-dimenzionální Euklidovský prostor, být doménou funkce${ displaystyle f: mathbb {R} ^ {N} rightarrow (- infty, + infty]}$. Předpokládat ${ displaystyle C}$ je neprázdná konvexní podmnožina ${ displaystyle mathbb {R} ^ {N}}$. Poté funkce indikátoru ${ displaystyle C}$ je definován jako

${ displaystyle iota _ {C}: x mapsto { begin {cases} 0 & { text {if}} x in C + infty & { text {if}} x notin C end {případy}}}$

${ displaystyle p}$-norm je definován jako ( ${ displaystyle | cdot | _ {p}}$ )

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

Vzdálenost od ${ displaystyle x in mathbb {R} ^ {N}}$ na ${ displaystyle C}$ je definován jako

${ displaystyle D_ {C} (x) = min _ {y v C} | x-y | _ {2}}$

Li ${ displaystyle C}$ je uzavřený a konvexní, projekce ${ displaystyle x in mathbb {R} ^ {N}}$ na ${ displaystyle C}$ je jedinečný bod${ displaystyle P_ {C} x v C}$ takhle ${ displaystyle D_ {C} (x) = | x-P_ {C} x | _ {2}}$.

The subdiferenciální z ${ displaystyle f}$ v ${ displaystyle x}$ je dána

${ displaystyle částečný f (x) = {u v mathbb {R} ^ {N} uprostřed pro všechny y in mathbb {R} ^ {N}, (yx) ^ { mathrm {T }} u + f (x) leq f (y). }}$

Projekce na konvexní sady (POCS)

Jedním z široce používaných konvexních optimalizačních algoritmů je projekce na konvexní sady (POCS). Tento algoritmus se používá k obnovení / syntéze signálu splňujícího současně několik konvexních omezení. Nechat ${ displaystyle f_ {i}}$ být indikátorovou funkcí neprázdné uzavřené konvexní množiny ${ displaystyle C_ {i}}$ modelování omezení. To se redukuje na konvexní problém proveditelnosti, který vyžaduje, abychom našli řešení tak, aby spočívalo v průsečíku všech konvexních množin ${ displaystyle C_ {i}}$. V metodě POCS každá sada ${ displaystyle C_ {i}}$ je začleněna do operátor projekce ${ displaystyle P_ {C_ {i}}}$. Takže v každém opakování ${ displaystyle x}$ je aktualizován jako

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

Kromě těchto problémů operátory projekce nejsou vhodné a k jejich řešení je zapotřebí obecnějších provozovatelů. Z různých zobecnění pojmu konvexní operátor projekce, které existují, jsou operátory přiblížení nejvhodnější pro jiné účely.

Definice

The operátor přiblížení konvexní funkce ${ displaystyle f}$ v ${ displaystyle x}$ je definováno jako jedinečné řešení

${ displaystyle operatorname {argmin} limity _ {y} { bigg (} f (y) + { frac {1} {2}} vlevo | xy vpravo | _ {2} ^ {2 } { bigg)}}$

a je označen ${ displaystyle operatorname {prox} _ {f} (x)}$.

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

Všimněte si, že v konkrétním případě, kde ${ displaystyle f}$ je indikátorová funkce ${ displaystyle iota _ {C}}$ nějaké konvexní množiny ${ displaystyle C}$

${ displaystyle { begin {aligned} operatorname {prox} _ { iota _ {C}} (x) & = operatorname {argmin} limits _ {y} { begin {cases} { 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 {zarovnáno}}}$

ukazující, že operátor přiblížení je skutečně zobecněním operátoru projekce.

Provozovatel blízkosti z ${ displaystyle f}$ je charakterizována inkluzí

${ displaystyle p = operatorname {prox} _ {f} (x) Leftrightarrow xp in částečný f (p) qquad ( forall (x, p) in mathbb {R} ^ {N} krát mathbb {R} ^ {N})}$

Li ${ displaystyle f}$ je diferencovatelné, pak výše uvedená rovnice klesá na

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

Příklady

Speciální instance metod proximálního gradientu jsou

• Projektovaný Landweber
• Střídavá projekce
• Metoda multiplikátorů střídavým směrem

Viz také

• Střídavá projekce
• Konvexní optimalizace
• Frank – Wolfeův algoritmus
• Proximální operátor
• Metody proximálního gradientu pro učení

Poznámky

Reference

• Rockafellar, R. T. (1970). Konvexní analýza. Princeton: Princeton University Press.
• Combettes, Patrick L .; Pesquet, Jean-Christophe (2011). Springerovy algoritmy s pevným bodem pro inverzní problémy ve vědě a inženýrství. 49. 185–212.

externí odkazy

• Kniha Stephen Boyd a Lieven Vandenberghe, Konvexní optimalizace
• EE364a: Konvexní optimalizace I a EE364b: Konvexní optimalizace II, Domovské stránky kurzu ve Stanfordu
• EE227A: Lieven Vandenberghe Notes Přednáška 18
• ProximalOperators.jl: a Julie balíček implementující proximální operátory.
• ProximalAlgorithms.jl: a Julie balíček implementující algoritmy založené na proximálním operátoru, včetně metody proximálního gradientu.
• Úložiště provozovatele přiblížení: kolekce operátorů přiblížení implementovaných v Matlab a Krajta.