Método del gradiente proximal

Los métodos de gradiente proximal son una forma generalizada de proyección utilizada para resolver problemas de optimización convexa no diferenciables .

Una comparación entre las iteraciones del método de gradiente proyectado (en rojo) y el método de Frank-Wolfe (en verde).

Muchos problemas interesantes pueden formularse como problemas de optimización convexa de la forma

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

donde son posibles funciones convexas no diferenciables . La falta de diferenciabilidad descarta las técnicas de optimización suave convencionales como el método de descenso más pronunciado y el método de gradiente conjugado , pero se pueden utilizar en su lugar métodos de gradiente proximal. ${\displaystyle f_{i}:\mathbb {R} ^{N}\rightarrow \mathbb {R} ,\ i=1,\dots ,n}$

Los métodos de gradiente proximal comienzan con un paso de división, en el que las funciones se utilizan individualmente para producir un algoritmo fácilmente implementable. Se denominan proximales porque cada función no diferenciable entre ellas está involucrada a través de su operador de proximidad . Algoritmo de umbralización de contracción iterativa, ^[1] Landweber proyectado , gradiente proyectado, proyecciones alternadas , método de multiplicadores de dirección alternada , Bregman de división alternada son instancias especiales de algoritmos proximales. ^[2] ${\displaystyle f_{1},...,f_{n}}$ ${\displaystyle f_{1},...,f_{n}}$

Para conocer la teoría de los métodos de gradiente proximal desde la perspectiva de la teoría del aprendizaje estadístico y con aplicaciones en ella , consulte métodos de gradiente proximal para el aprendizaje .

Proyección sobre conjuntos convexos (POCS)

Uno de los algoritmos de optimización convexa más utilizados es el de proyecciones sobre conjuntos convexos (POCS). Este algoritmo se emplea para recuperar/sintetizar una señal que satisface simultáneamente varias restricciones convexas. Sea la función indicadora de un conjunto convexo cerrado no vacío que modela una restricción. Esto se reduce al problema de viabilidad convexa, que requiere que encontremos una solución que se encuentre en la intersección de todos los conjuntos convexos . En el método POCS, cada conjunto se incorpora mediante su operador de proyección . Por lo tanto, en cada iteración se actualiza como ${\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}}$

Sin embargo, más allá de estos problemas, los operadores de proyección no son apropiados y se requieren operadores más generales para abordarlos. Entre las diversas generalizaciones de la noción de operador de proyección convexo que existen, los operadores proximales son los más adecuados para otros fines.

Ejemplos

Ejemplos especiales de métodos de gradiente proximal son

• Landweber proyectado
• Proyección alternada
• Método de multiplicadores de dirección alternada

Véase también

• Operador proximal
• Métodos de gradiente proximal para el aprendizaje
• Algoritmo de Frank-Wolfe

Notas

1. Daubechies, I; Defrise, M; De Mol, C (2004). "Un algoritmo de umbralización iterativo para problemas inversos lineales con una restricción de escasez". Communications on Pure and Applied Mathematics . 57 (11): 1413–1457. arXiv : math/0307152 . Bibcode :2003math......7152D. doi :10.1002/cpa.20042.
2. Los métodos proximales se analizan en detalle en Combettes, Patrick L.; Pesquet, Jean-Christophe (2009). "Métodos de división proximal en el procesamiento de señales". arXiv : 0912.3522 [math.OC].

Referencias

• Rockafellar, RT (1970). Análisis convexo . Princeton: Princeton University Press.
• Combettes, Patrick L.; Pesquet, Jean-Christophe (2011). Algoritmos de punto fijo para problemas inversos en ciencia e ingeniería . Vol. 49. págs. 185–212.

Enlaces externos

• Libro de Stephen Boyd y Lieven Vandenberghe, Optimización convexa
• EE364a: Optimización convexa I y EE364b: Optimización convexa II, páginas de inicio de cursos de Stanford
• EE227A: Lieven Vandenberghe Notas Conferencia 18
• ProximalOperators.jl: un paquete de Julia que implementa operadores proximales.
• ProximalAlgorithms.jl: un paquete de Julia que implementa algoritmos basados ​​en el operador proximal, incluido el método de gradiente proximal.
• Repositorio de operadores de proximidad: una colección de operadores de proximidad implementados en Matlab y Python .