Proksimal gradientmetode

Den proksimale gradientmetode [1] er en generalisering af projektion, der bruges til at løse ikke-differentierbare konvekse programmeringsproblemer .

Mange interessante problemer kan formuleres som konvekse programmeringsproblemer af formen

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

hvor er konvekse funktioner , defineret som afbildninger , hvor nogle af funktionerne er ikke-differentierbare, hvilket udelukker de sædvanlige glatte optimeringsteknikker, såsom den stejleste nedstigningsmetode eller den konjugerede gradientmetode osv., kan proksimale gradientmetoder bruges i stedet. Disse metoder fungerer ved at opdele, så funktionerne bruges individuelt, hvilket muliggør udvikling af lettere implementerede algoritmer. De kaldes proksimale ( eng. proximal , nærmeste), da hver ikke -glat funktion blandt er involveret i processen gennem nærhedsoperatøren. Iterativ blød tærskelfiltreringsalgoritme $f_{i},\ i=1,\dots ,n$ $f:\mathbb {R} ^{N}\rightarrow \mathbb {R}$ $f_{1},...,f_{n}$ $f_{1},...,f_{n}$ [2] , Landweber projektion , gradient projektion , alternerende projektioner , metoden til alternerende retninger af multiplikatorer , metoden til alternerende opdelinger af Bragman er specielle tilfælde af proksimale algoritmer [3] . For en diskussion af proksimale gradientmetoder ud fra perspektivet af statistisk læringsteori og anvendelser til denne teori, se Proksimale gradientmetoder til maskinlæring .

Notation og terminologi

Lad , -dimensionelle euklidiske rum , være funktionens domæne . Antag, at det er en ikke-tom konveks delmængde af sættet . Så er sættets indikatorfunktion defineret som $\mathbb {R} ^{N}$ $N$ $f:\mathbb {R} ^{N}\højrepil (-\infty ,+\infty ]$ $C$ $\mathbb {R} ^{N}$ $C$

\iota _{C}:x\mapsto {\begin{cases}0&&x\in C\\+\infty &&x\notin C\end{cases}}

s

-norm defineres som

(\|\cdot \|_{p})

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

Afstanden fra til er defineret som $x\in \mathbb {R} ^{N}$ $C$

{\displaystyle D_{C}(x)=\min _{y\in C}\|xy\|_{2))

Hvis er lukket og konveks, er projektionen til sættet det eneste punkt, således at . $C$ $x\in \mathbb {R} ^{N}$ $C$ $P_{C}x\in C$ ${\displaystyle D_{C}(x)=\|x-P_{C}x\|_{2))$

Subdifferentialet for en funktion i et punkt er givet af udtrykket $f$ $x$

\partial f(x)=\{u\in \mathbb {R} ^{N}\mid \forall y\in \mathbb {R} ^{N},(yx)^{\mathrm {T } }u+f(x)\leqslant f(y).\}

Projektion til konvekse sæt

En meget brugt konveks optimeringsalgoritme er projektion til konvekse sæt . Denne algoritme bruges til at detektere/syntetisere et signal, der opfylder flere konvekse begrænsninger samtidigt. Lad være en indikatorfunktion på et ikke-tomt lukket konveks sæt, der modellerer en begrænsning. Dette reducerer problemet til problemet med konveks gennemførlighed (reachability), hvor man skal finde en løsning indeholdt i skæringspunktet mellem alle konvekse sæt . I metoden til projektion til konvekse sæt er hvert sæt forbundet med dets projektor . Således genberegnes ved hver iteration efter formlen $f_{i}$ $C_{i}$ $C_{i}$ $C_{i}$ $P_{C_{i))$ $x$

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

Ud over sådanne opgaver er projektorer dog ikke egnede, og der kræves operatører af en mere generel form. Blandt de forskellige eksisterende generaliseringer af begrebet en konveks projektor er nærhedsoperatører bedst egnede til sådanne formål.

Definition

Nærhedsoperatoren for en konveks funktioni et punkter defineret som den eneste løsning $f$ $x$

{\displaystyle \operatorname {argmin} \limits _{y}{\bigg (}f(y)+{\frac {1}{2}}\left\|xy\right\|_{2}^{2 }{\bigg)))

og er betegnet som . $\operatørnavn {prox} _{f}(x)$

{\displaystyle \operatorname {prox} _{f}(x):\mathbb {R} ^{N}\højrepil \mathbb {R} ^{N))

Bemærk, at i tilfælde af hvornår er indikatorfunktionen for nogle konvekse sæt $f$ $\iota _{C}$ $C$

{\begin{aligned}\operatørnavn {prox} _{\iota _{C}}(x)&=\operatørnavn {argmin} \limits _{y}{\begin{cases}{\frac {1 }{2}}\left\|xy\right\|_{2}^{2}&&y\in C\\+\infty &&y\notin C\end{cases}}\\&=\operatørnavn {argmin} \limits _{y\in C}{\frac {1}{2}}\left\|xy\right\|_{2}^{2}\\&=P_{C}(x)\end{ justeret}}

hvilket viser, at nærhedsoperatøren faktisk er en generalisering af projektoren.

Funktionen nærhedsoperatør er beskrevet ved inklusion $f$

p=\operatørnavn {prox} _{f}(x)\Leftrightarrow xp\in \partial f(p)\qquad (\forall (x,p)\in \mathbb {R} ^{N}\ gange \mathbb {R} ^{N})

Hvis der kan differentieres, reduceres ligningen ovenfor til $f$

p=\operatørnavn {prox} _{f}(x)\Leftrightarrow xp=\nabla f(p)\quad (\forall (x,p)\in \mathbb {R} ^{N}\times \mathbb {R} ^{N})

Eksempler

Særlige tilfælde af proksimale gradientmetoder er

Landweber projektion
Alternativ projektion
metode til alternerende retninger af multiplikatorer

Se også

Noter

↑ Engelsk. Proksimalt = tættest på
↑ Daubechies, Defrise, De Mol, 2004 , s. 1413-1457
↑ Proksimale metoder diskuteres i detaljer

Litteratur

Daubechies I., Defrise M., De Mol C. En iterativ tærskelalgoritme for lineære inverse problemer med en sparsitetsbegrænsning // Communications on Pure and Applied Mathematics. - 2004. - T. 57 , no. 11 . - doi : 10.1002/cpa.20042 . - . - arXiv : math/0307152 .
Rockafellar RT Konveks analyse. — Princeton: Princeton University Press, 1970.
Patrick L. Combettes, Jean-Christophe Pesquet. Springers fastpunktsalgoritmer for omvendte problemer i videnskab og teknik. - 2011. - T. 49. - S. 185-212.