Método lagrangiano aumentado

Clase de algoritmos para resolver problemas de optimización restringida

Los métodos lagrangianos aumentados son una clase determinada de algoritmos para resolver problemas de optimización con restricciones . Tienen similitudes con los métodos de penalización en el sentido de que reemplazan un problema de optimización con restricciones por una serie de problemas sin restricciones y añaden un término de penalización al objetivo , pero el método lagrangiano aumentado añade otro término diseñado para imitar un multiplicador de Lagrange . El lagrangiano aumentado está relacionado con el método de los multiplicadores de Lagrange , pero no es idéntico a él .

Visto de otra manera, el objetivo sin restricciones es el lagrangiano del problema restringido, con un término de penalización adicional (el aumento ).

El método se conocía originalmente como el método de multiplicadores y se estudió en los años 1970 y 1980 como una alternativa potencial a los métodos de penalización. Fue discutido por primera vez por Magnus Hestenes ^[1] y luego por Michael Powell en 1969. ^[2] El método fue estudiado por R. Tyrrell Rockafellar en relación con la dualidad de Fenchel , particularmente en relación con los métodos de punto proximal, la regularización de Moreau-Yosida y los operadores monótonos máximos ; estos métodos se utilizaron en optimización estructural . El método también fue estudiado por Dimitri Bertsekas , en particular en su libro de 1982, ^[3] junto con extensiones que involucran funciones de regularización no cuadráticas (por ejemplo, regularización entrópica ). Este estudio combinado da lugar al "método exponencial de multiplicadores" que maneja restricciones de desigualdad con una función lagrangiana aumentada dos veces diferenciable.

Desde la década de 1970, se ha prestado más atención a la programación cuadrática secuencial (SQP) y a los métodos de puntos interiores (IPM), en parte porque utilizan más fácilmente subrutinas de matriz dispersa de bibliotecas de software numérico , y en parte porque los IPM poseen resultados de complejidad probados a través de la teoría de funciones autoconcordantes . El método lagrangiano aumentado fue rejuvenecido por los sistemas de optimización LANCELOT , ALGENCAN ^{[4] [5]} y AMPL , que permitieron utilizar técnicas de matriz dispersa en problemas aparentemente densos pero "parcialmente separables". El método sigue siendo útil para algunos problemas. ^[6]

Alrededor de 2007, hubo un resurgimiento de los métodos lagrangianos aumentados en campos como la eliminación de ruido de la variación total y la detección comprimida . En particular, una variante del método lagrangiano aumentado estándar que utiliza actualizaciones parciales (similar al método de Gauss-Seidel para resolver ecuaciones lineales) conocida como el método de dirección alternada de multiplicadores o ADMM ganó cierta atención.

Método general

Consideremos resolver el siguiente problema de optimización restringida:

${\displaystyle \min f(\mathbf {x} )}$

sujeto a

${\displaystyle c_{i}(\mathbf {x} )=0~\forall i\in {\mathcal {E}},}$

donde denota los índices de las restricciones de igualdad. Este problema se puede resolver como una serie de problemas de minimización sin restricciones. Como referencia, primero enumeramos el k- ésimo paso del enfoque del método de penalización : ${\displaystyle {\mathcal {E}}}$

${\displaystyle \min \Phi _{k}(\mathbf {x} )=f(\mathbf {x} )+\mu _{k}~\sum _{i\in {\mathcal {E}}}~c_{i}(\mathbf {x} )^{2}.}$

El método de penalización resuelve este problema y luego, en la siguiente iteración, vuelve a resolver el problema utilizando un valor mayor de y utilizando la solución anterior como la estimación inicial o "inicio en caliente". ${\displaystyle \mu _{k}}$

El método lagrangiano aumentado utiliza el siguiente objetivo sin restricciones:

${\displaystyle \min \Phi _{k}(\mathbf {x} )=f(\mathbf {x} )+{\frac {\mu _{k}}{2}}~\sum _{i\in {\mathcal {E}}}~c_{i}(\mathbf {x} )^{2}+\sum _{i\in {\mathcal {E}}}~\lambda _{i}c_{i}(\mathbf {x} )}$

y después de cada iteración, además de actualizarse , la variable también se actualiza según la regla ${\displaystyle \mu _{k}}$ ${\displaystyle \lambda }$

${\displaystyle \lambda _{i}\leftarrow \lambda _{i}+\mu _{k}c_{i}(\mathbf {x} _{k})}$

donde es la solución del problema sin restricciones en el k -ésimo paso (es decir, ). ${\displaystyle \mathbf {x} _{k}}$ ${\displaystyle \mathbf {x} _{k}={\text{argmin}}\Phi _{k}(\mathbf {x} )}$

La variable es una estimación del multiplicador de Lagrange y la precisión de esta estimación mejora en cada paso. La principal ventaja del método es que, a diferencia del método de penalización , no es necesario tomar para resolver el problema restringido original. Debido a la presencia del término multiplicador de Lagrange, puede permanecer mucho más pequeño y, por lo tanto, evitar el mal condicionamiento. ^[6] Sin embargo, es común en las implementaciones prácticas proyectar estimaciones de multiplicadores en un gran conjunto acotado (salvaguardas) que evita inestabilidades numéricas y conduce a una fuerte convergencia teórica. ^[5] ${\displaystyle \lambda }$ ${\displaystyle \mu \rightarrow \infty }$ ${\displaystyle \mu }$

El método se puede ampliar para manejar restricciones de desigualdad. Para una discusión de mejoras prácticas, véanse las referencias ^{[6] [5]}

Método de dirección alternada de multiplicadores

El método de multiplicadores de dirección alternada (ADMM) es una variante del esquema lagrangiano aumentado que utiliza actualizaciones parciales para las variables duales. Este método se aplica a menudo para resolver problemas como:

${\displaystyle \min _{x}f(x)+g(x).}$

Esto es equivalente al problema restringido,

${\displaystyle \min _{x,y}f(x)+g(y),\quad {\text{subject to}}\quad x=y.}$

Aunque este cambio puede parecer trivial, el problema ahora puede ser atacado usando métodos de optimización restringida (en particular, el método lagrangiano aumentado), y la función objetivo es separable en x e y . La actualización dual requiere resolver una función de proximidad en x e y al mismo tiempo; la técnica ADMM permite que este problema se resuelva aproximadamente resolviendo primero para x con y fijo y luego resolviendo para y con x fijo. En lugar de iterar hasta la convergencia (como el método de Jacobi ), el algoritmo procede directamente a actualizar la variable dual y luego repite el proceso. Esto no es equivalente a la minimización exacta, pero el método aún converge a la solución correcta bajo algunas suposiciones. Debido a esta aproximación, el algoritmo es distinto del método lagrangiano aumentado puro.

El ADMM puede verse como una aplicación del algoritmo de división de Douglas-Rachford, y el algoritmo de Douglas-Rachford es a su vez una instancia del algoritmo de punto proximal; los detalles se pueden encontrar en la referencia ^[7] . Hay varios paquetes de software modernos, incluidos YALL1 ^[8] (2009), SpaRSA ^[9] (2009) y SALSA ^[10] (2009), que resuelven la búsqueda de base y variantes y utilizan el ADMM. También hay paquetes que utilizan el ADMM para resolver problemas más generales, algunos de los cuales pueden explotar múltiples núcleos de computación (por ejemplo, SNAPVX ^[11] (2015), parADMM ^[12] (2016)).

Optimización estocástica

La optimización estocástica considera el problema de minimizar una función de pérdida con acceso a muestras ruidosas de la función (gradiente de la misma). El objetivo es tener una estimación del parámetro óptimo (minimizador) por cada nueva muestra. Con algunas modificaciones, ADMM se puede utilizar para la optimización estocástica. En un entorno estocástico, solo se puede acceder a muestras ruidosas de un gradiente, por lo que se utiliza una aproximación inexacta del lagrangiano:

${\displaystyle {\hat {\mathcal {L}}}_{\rho ,k}=f_{1}(x_{k})+\langle \nabla f(x_{k},\zeta _{k+1}),x\rangle +g(y)-z^{T}(Ax+By-c)+{\frac {\rho }{2}}\Vert Ax+By-c\Vert ^{2}+{\frac {\Vert x-x_{k}\Vert ^{2}}{2\eta _{k+1}}},}$

donde es un tamaño de paso que varía con el tiempo. ^[13] ${\displaystyle \eta _{k+1}}$

ADMM se ha aplicado para resolver problemas regularizados, donde la optimización y regularización de funciones se pueden realizar localmente y luego coordinar globalmente a través de restricciones. ^{[14] [15] [16] [17]}

Los problemas de optimización regularizados son especialmente relevantes en el régimen de alta dimensión, ya que la regularización es un mecanismo natural para superar la falta de precisión y fomentar la parsimonia en la solución óptima (por ejemplo, escasez y rango bajo). La eficacia de ADMM para resolver problemas regularizados puede significar que podría ser útil para resolver problemas de optimización estocástica de alta dimensión. ^[18]

Enfoques alternativos

• Programación cuadrática secuencial
• Programación lineal secuencial
• Programación lineal-cuadrática secuencial

Software

Implementaciones de código abierto y no libres/comerciales del método lagrangiano aumentado:

• Accord.NET (Implementación en C# del optimizador lagrangiano aumentado)
• ALGLIB (implementaciones en C# y C++ del solucionador lagrangiano aumentado preacondicionado)
• PENNON (GPL 3, licencia comercial disponible)
• LANCELOT (licencia gratuita de "uso interno", opciones comerciales pagas)
• MINOS (también utiliza un método lagrangiano aumentado para algunos tipos de problemas).
• El código para REASON con licencia Apache 2.0 está disponible en línea. ^[19]
• ALGENCAN (Implementación en Fortran del método lagrangiano aumentado con salvaguardas). Disponible en línea. ^[20]
• NLOPT (implementación en C++ del optimizador lagrangiano aumentado, accesible desde diferentes lenguajes de programación ^{[21] [22]} ) ^[23]
• PyProximal (implementación en Python del método lagrangiano aumentado). ^[24]

Véase también

• Función de barrera
• Método de puntos interiores
• Multiplicador de Lagrange
• Método de penalización

Referencias

1. Hestenes, MR (1969). "Métodos de multiplicadores y gradientes". Revista de teoría y aplicaciones de optimización . 4 (5): 303–320. doi :10.1007/BF00927673. S2CID  121584579.
2. Powell, MJD (1969). "Un método para restricciones no lineales en problemas de minimización". En Fletcher, R. (ed.). Optimización . Nueva York: Academic Press. págs. 283–298. ISBN 0-12-260650-7.
3. Bertsekas, Dimitri P. (1996) [1982]. Optimización restringida y métodos multiplicadores de Lagrange . Athena Scientific.
4. Andreani, R.; Birgin, EG; Martínez, JM; Schuverdt, ML (2007). "Sobre métodos lagrangianos aumentados con restricciones generales de nivel inferior". Revista SIAM sobre optimización . 18 (4): 1286–1309. doi :10.1137/060654797. S2CID  1218538.
5. Birgin y Martínez (2014)
6. Nocedal y Wright (2006), capítulo 17
7. Eckstein, J.; Bertsekas, DP (1992). "Sobre el método de división de Douglas—Rachford y el algoritmo del punto proximal para operadores monótonos máximos". Programación matemática . 55 (1–3): 293–318. CiteSeerX 10.1.1.141.6246 . doi :10.1007/BF01581204. S2CID  15551627. 
8. "YALL1: Sus algoritmos para L1". yall1.blogs.rice.edu .
9. "SpaRSA". www.lx.it.pt .
10. "(C)SALSA: Un solucionador para problemas de optimización convexa en recuperación de imágenes". cascais.lx.it.pt .
11. "SnapVX". snap.stanford.edu .
12. "parADMM/engine". 6 de febrero de 2021 – vía GitHub.
13. Ouyang, H.; He, N.; Tran, L. y Gray, A. G (2013). "Método de multiplicadores de dirección alterna estocástica". Actas de la 30.ª Conferencia internacional sobre aprendizaje automático : 80–88.
14. Boyd, S.; Parikh, N.; Chu, E.; Peleato, B. y Eckstein, J. (2011). "Optimización distribuida y aprendizaje estadístico a través del método de dirección alternada de multiplicadores". Fundamentos y tendencias en aprendizaje automático . 3 (1): 1–122. CiteSeerX 10.1.1.360.1664 . doi :10.1561/2200000016. S2CID  51789432. 
15. Wahlberg, B.; Boyd, S.; Annergren, M.; Wang, Y. (2012). "Un algoritmo ADMM para una clase de problemas de estimación regularizada de variación total". arXiv : 1203.1828 [stat.ML].
16. Esser, E.; Zhang, X.; Chan, T. (2010). "Un marco general para una clase de algoritmos primal-dual de primer orden para la optimización convexa en la ciencia de la imagen". Revista SIAM sobre Ciencias de la Imagen . 3 (4): 1015–1046. doi :10.1137/09076934X.
17. Mota, J. FC; Xavier, J. MF; Aguiar, P. MQ; Puschel, M. (2012). "ADMM distribuido para control predictivo de modelos y control de congestión". 2012 IEEE 51st IEEE Conference on Decision and Control (CDC) . págs. 5110–5115. doi :10.1109/CDC.2012.6426141. ISBN 978-1-4673-2066-5.S2CID12128421  .​
18. "Método de dirección alternada de multiplicadores: descripción general | Temas de ScienceDirect" www.sciencedirect.com . Consultado el 7 de agosto de 2023 .
19. "Bitbucket". bitbucket.org .
20. "Proyecto TANGO". www.ime.usp.br .
21. Stamm, Aymeric (15 de julio de 2022), nloptr , consultado el 19 de julio de 2022
22. El módulo NLopt para Julia, JuliaOpt, 25 de junio de 2022 , consultado el 19 de julio de 2022
23. Johnson, Steven G. (14 de julio de 2022), stevengj/nlopt , consultado el 19 de julio de 2022
24. "Proyecto PyProximal". www.github.com/PyLops/pyproximal .

Bibliografía

• Bertsekas, Dimitri P. (1999), Programación no lineal (2.ª ed.), Belmont, Mass: Athena Scientific , ISBN 978-1-886529-00-7
• Birgin, EG; Martínez, JM (2014), Métodos prácticos de Lagrangian aumentados para optimización restringida , Filadelfia: Society for Industrial and Applied Mathematics , doi : 10.1137/1.9781611973365 , ISBN 978-1-611973-35-8
• Nocedal, Jorge; Wright, Stephen J. (2006), Optimización numérica (2.ª ed.), Berlín, Nueva York: Springer-Verlag , ISBN 978-0-387-30303-1