Metoda gradientului proximal

Metoda gradientului proximal [1] este o generalizare a proiecției utilizată pentru a rezolva probleme de programare convexă nediferențiabilă .

Multe probleme interesante pot fi formulate ca probleme de programare convexe ale formei

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

unde sunt funcții convexe , definite ca mapări , unde unele dintre funcții sunt nediferențiabile, ceea ce exclude tehnicile obișnuite de optimizare netedă, cum ar fi metoda cea mai abruptă de coborâre sau metoda gradientului conjugat etc., se pot folosi în schimb metodele gradientului proximal. Aceste metode funcționează prin împărțire, astfel încât funcțiile să fie utilizate individual, permițând dezvoltarea unor algoritmi mai ușor de implementat. Ele sunt numite proximale ( eng. proximal , cea mai apropiată), deoarece fiecare funcție non-smooth dintre este implicată în proces prin operatorul de proximitate. Algoritmul iterativ de filtrare soft threshold [2] , proiecția Landweber , proiecția gradientului , proiecțiile alternante , metoda direcțiilor alternante ale multiplicatorilor , metoda divizărilor alternante ale lui Bragman sunt cazuri speciale de algoritmi proximali [3] . Pentru o discuție despre metodele de gradient proximal din perspectiva teoriei învățării statistice și a aplicațiilor acestei teorii, vezi Metode de gradient proximal pentru învățarea automată . $f_{i},\i=1,\dots ,n$ $f:\mathbb {R} ^{N}\rightarrow \mathbb {R}$ $f_{1},...,f_{n}$ $f_{1},...,f_{n}$

Notație și terminologie

Fie , spațiu euclidian -dimensional , domeniul funcției . Să presupunem că este o submulțime convexă nevidă a mulțimii . Apoi funcția indicator a setului este definită ca $\mathbb {R} ^{N}$ $N$ $f:\mathbb {R} ^{N}\rightarrow (-\infty ,+\infty ]$ $C$ $\mathbb {R} ^{N}$ $C$

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

p

-norma este definită ca

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

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

Distanța de la până este definită ca $x\in \mathbb {R} ^{N}$ $C$

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

Dacă este închis și convex, proiecția către mulțime este singurul punct astfel încât . $C$ $x\in \mathbb {R} ^{N}$ $C$ $P_{C}x\in C$ $D_{C}(x)=\|x-P_{C}x\|_{2)$

Subdiferenţialul unei funcţii într-un punct este dat de expresia $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).\}

Proiecție la mulțimi convexe

Un algoritm de optimizare convex utilizat pe scară largă este proiecția la mulțimi convexe . Acest algoritm este folosit pentru a detecta/sintetiza un semnal care satisface mai multe constrângeri convexe simultan. Fie o funcție indicator pe o mulțime convexă închisă nevide care modelează o constrângere. Aceasta reduce problema la problema fezabilității convexe (accesibilitatea), în care trebuie să găsim o soluție conținută în intersecția tuturor mulțimilor convexe . În metoda de proiecție la seturi convexe, fiecare set este asociat cu proiectorul său . Astfel, la fiecare iterație se recalculează conform formulei $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}

Cu toate acestea, dincolo de astfel de sarcini, proiectoarele nu sunt potrivite și sunt necesari operatori de o formă mai generală. Dintre diferitele generalizări existente ale noțiunii de proiector convex, operatorii de proximitate sunt cei mai potriviți pentru astfel de scopuri.

Definiție

Operatorul de proximitate al unei funcții convexeîntr-un puncteste definit ca singura soluție $f$ $X$

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

și este notat ca . $\operatorname {prox} _{f}(x)$

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

Rețineți că, în cazul în care este funcția indicator a unui set convex $f$ $\iota _{C}$ $C$

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

ceea ce arată că operatorul de proximitate este într-adevăr o generalizare a proiectorului.

Operatorul de proximitate al funcției este descris de includere $f$

p=\operatorname {prox} _{f}(x)\Leftrightarrow xp\in \partial f(p)\qquad (\forall (x,p)\in \mathbb {R} ^{N}\ ori \mathbb {R} ^{N})

Dacă este diferențiabilă, atunci ecuația de mai sus se reduce la $f$

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

Exemple

Cazuri particulare de metode de gradient proximal sunt

proiecție Landweber
proiecție alternativă
metoda de alternare a directiilor multiplicatorilor

Vezi și

Note

↑ engleză. Proximal = cel mai apropiat
↑ Daubechies, Defrise, De Mol, 2004 , p. 1413–1457
^ Patrick L. Combettes Metodele proximale sunt discutate în detaliu

Literatură

Daubechies I., Defrise M., De Mol C. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint // Communications on Pure and Applied Mathematics. - 2004. - T. 57 , nr. 11 . - doi : 10.1002/cpa.20042 . - Cod biblic . - arXiv : math/0307152 .
Analiza Rockafellar RT Convex. — Princeton: Princeton University Press, 1970.
Patrick L. Combettes, Jean-Christophe Pesquet. Algoritmi cu punct fix a lui Springer pentru probleme inverse în știință și inginerie. - 2011. - T. 49. - S. 185–212.

Link -uri

Stephen Boyd, Lieven Vandenberghe, Optimizare convexă
EE364a: Optimizare convexă I și EE364b: Optimizare convexă II , pagini de curs Stanford
EE227A: Lieven Vandenberghe Note Lectura 18
ProximalOperators.jl : Un pachet Julia care implementează operatori proximali.
ProximalAlgorithms.jl : Un pachet Julia care implementează algoritmi bazați pe operatori de proximitate, inclusiv metoda gradientului proximal.
Depozitul operator de proximitate : O colecție de operatori de proximitate implementați în Matlab și Python .