Método de gradiente proximal

El método del gradiente proximal [1] es una generalización de la proyección utilizada para resolver problemas de programación convexa no diferenciables .

Muchos problemas interesantes se pueden formular como problemas de programación convexa de la forma

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

donde son funciones convexas , definidas como mapeos , donde algunas de las funciones no son diferenciables, lo que excluye las técnicas habituales de optimización suave, como el método de descenso más pronunciado o el método de gradiente conjugado , etc., se pueden usar métodos de gradiente proximal en su lugar. Estos métodos funcionan por división para que las funciones se utilicen individualmente, lo que permite el desarrollo de algoritmos más fáciles de implementar. Se denominan proximales ( ing. proximal , más cercano), ya que cada función no suave entre ellas está involucrada en el proceso a través del operador de proximidad. Algoritmo iterativo de filtrado de umbral suave $f_{i},\i=1,\puntos,n$ $f:\mathbb {R} ^{N}\rightarrow \mathbb {R}$ ${\ estilo de visualización f_ {1},..., f_ {n}}$ ${\ estilo de visualización f_ {1},..., f_ {n}}$ [2] , la proyección de Landweber , la proyección de gradientes , las proyecciones alternas , el método de direcciones alternas de multiplicadores , el método de desdoblamientos alternos de Bragman son casos especiales de algoritmos proximales [3] . Para obtener una discusión sobre los métodos de gradiente proximal desde la perspectiva de la teoría del aprendizaje estadístico y las aplicaciones de esta teoría, consulte Métodos de gradiente proximal para el aprendizaje automático .

Notación y terminología

Sea el espacio euclidiano bidimensional el dominio de la función . Supongamos que es un subconjunto convexo no vacío del conjunto . Entonces la función indicadora del conjunto se define como ${\ estilo de visualización \ mathbb {R} ^ {N}}$ $norte$ $f:\mathbb {R} ^{N}\rightarrow (-\infty,+\infty]$ $C$ ${\ estilo de visualización \ mathbb {R} ^ {N}}$ $C$

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

pags

-la norma se define como

{\ estilo de visualización (\|\ cdot \|_{p})}

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

La distancia de a se define como $x\en \mathbb {R} ^{N}$ $C$

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

Si es cerrado y convexo, la proyección al conjunto es el único punto tal que . $C$ $x\en \mathbb {R} ^{N}$ $C$ $P_{C}x\en C$ ${\displaystyle D_{C}(x)=\|x-P_{C}x\|_{2))$

La subdiferencial de una función en un punto viene dada por la expresión $F$ $X$

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

Proyección a conjuntos convexos

Un algoritmo de optimización convexo ampliamente utilizado es la proyección a conjuntos convexos . Este algoritmo se utiliza para detectar/sintetizar una señal que satisface varias restricciones convexas simultáneamente. Sea una función indicadora en un conjunto convexo cerrado no vacío que modela una restricción. Esto reduce el problema al problema de la factibilidad convexa (accesibilidad), en el que se necesita encontrar una solución contenida en la intersección de todos los conjuntos convexos . En el método de proyección a conjuntos convexos, cada conjunto está asociado a su proyector . Así, en cada iteración se recalcula según la fórmula $f_{i}$ $C_{yo}$ $C_{yo}$ $C_{yo}$ $P_{C_{i))$ $X$

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

Sin embargo, más allá de tales tareas, los proyectores no son adecuados y se requieren operadores de una forma más general. Entre las diversas generalizaciones existentes de la noción de un proyector convexo, los operadores de proximidad son los más adecuados para tales fines.

Definición

El operador de proximidad de una función convexaen un puntose define como la única solución $F$ $X$

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

y se denota como . ${\ estilo de visualización \ nombre del operador {prox} _ {f} (x)}$

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

Tenga en cuenta que en el caso cuando es la función indicadora de algún conjunto convexo $F$ ${\ estilo de visualización \ iota _ {C}}$ $C$

{\begin{alineado}\operatorname {prox}_{\iota_{C}}(x)&=\operatorname {argmin} \limits_{y}{\begin{casos}{\frac {1 }{2}}\left\|xy\right\|_{2}^{2}&&y\in 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{ alineado}}

lo que muestra que el operador de proximidad es de hecho una generalización del proyector.

El operador de proximidad de la función se describe mediante la inclusión $F$

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

Si es diferenciable, entonces la ecuación anterior se reduce a $F$

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

Ejemplos

Los casos particulares de métodos de gradiente proximal son

Proyección Landweber
Proyección alternativa
método de direcciones alternas de multiplicadores

Véase también

Notas

↑ Inglés. Proximal = más cercano
↑ Daubechies, Defrise, De Mol, 2004 , pág. 1413-1457
↑ Los métodos proximales se discuten en detalle.

Literatura

Daubechies I., Defrise M., De Mol C. Un algoritmo de umbral iterativo para problemas lineales inversos con una restricción de escasez // Comunicaciones sobre matemáticas puras y aplicadas. - 2004. - T. 57 , núm. 11 _ -doi : 10.1002/ cpa.20042 . - . -arXiv : matemáticas / 0307152 .
Rockafellar RT Análisis convexo. — Princeton: Prensa de la Universidad de Princeton, 1970.
Patrick L. Combettes, Jean-Christophe Pesquet. Algoritmos de punto fijo de Springer para problemas inversos en ciencia e ingeniería. - 2011. - T. 49. - S. 185-212.

Enlaces

Stephen Boyd, Lieven Vandenberghe, optimización convexa
EE364a: Optimización convexa I y EE364b: Optimización convexa II , páginas del curso de Stanford
EE227A: Lieven Vandenberghe anota la lección 18
ProximalOperators.jl : un paquete de Julia que implementa operadores proximales.
ProximalAlgorithms.jl : un paquete de Julia que implementa algoritmos basados en operadores de proximidad, incluido el método de gradiente proximal.
Repositorio de operadores de proximidad : una colección de operadores de proximidad implementados en Matlab y Python .