Método lagrangiano aumentado

Clase de algoritmos para resolver problemas de optimización restringida.

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

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

El método se conocía originalmente como método de los multiplicadores y se estudió en las décadas de 1970 y 1980 como una posible alternativa 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 operadores monótonos máximos ; Estos métodos se utilizaron en optimización estructural . El método también fue estudiado por Dimitri Bertsekas , notablemente 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 punto interior (IPM), en parte porque utilizan más fácilmente subrutinas matriciales dispersas 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 matrices dispersas 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 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) conocido como método de multiplicadores de dirección alterna o ADMM ganó cierta atención.

método general

Considere 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 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 suposició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})}$

¿Dónde está la solución al 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 evitar así un mal condicionamiento. ^[6] Sin embargo, es común en implementaciones prácticas proyectar estimaciones de multiplicadores en un gran conjunto acotado (salvaguardias), lo 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 sobre mejoras prácticas, consulte las refs. ^{[sesenta y cinco]}

Método de dirección alterna de multiplicadores.

El método de multiplicadores de dirección alterna (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 se puede atacar utilizando 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 xey al mismo tiempo ; la técnica ADMM permite resolver este problema aproximadamente resolviendo primero x con y fijo y luego resolviendo 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 equivale a la minimización exacta, pero el método aún converge a la solución correcta bajo algunos supuestos. 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 del punto proximal; Los detalles se pueden encontrar en la ref. ^[7] Existen varios paquetes de software modernos, incluidos YALL1 ^[8] (2009), SpaRSA ^[9] (2009) y SALSA ^[10] (2009), que resuelven la búsqueda de bases y variantes y utilizan ADMM. También hay paquetes que utilizan ADMM para resolver problemas más generales, algunos de los cuales pueden explotar múltiples núcleos informáticos (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 (gradiente de) función. El objetivo es tener una estimación del parámetro óptimo (minimizador) por nueva muestra. Con algunas modificaciones, ADMM se puede utilizar para optimización estocástica. En un entorno estocástico, sólo 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 en 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 llevar a cabo localmente y luego coordinarse globalmente mediante 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 las malas posiciones 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]

Aproximaciones alternativas

• 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++ de solucionador lagrangiano aumentado precondicionado)
• 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 Fortran del método Lagrangiano aumentado con salvaguardias). Disponible en linea. ^[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]

Ver también

• Función de barrera
• Método del punto interior
• multiplicador de Lagrange
• Método de penalización

Referencias

1. Hestenes, señor (1969). "Métodos 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" . Atenas científica.
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: Tus ALgoritmos para L1". yall1.blogs.rice.edu .
9. "SpaRSA". www.lx.it.pt.​
10. "(C)SALSA: una solución para problemas de optimización convexa en la recuperación de imágenes". cascais.lx.it.pt .
11. "SnapVX". snap.stanford.edu .
12. "parADMM/motor". 6 de febrero de 2021 – vía GitHub.
13. Ouyang, H.; Él, N.; Tran, L. y Gray, AG (2013). "Método estocástico de multiplicadores de dirección alterna". 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 mediante el método de multiplicadores de dirección alterna". Fundamentos y tendencias{\textregistered} 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 regularizados de variación total". arXiv : 1203.1828 [estad.ML].
16. Esser, E.; Zhang, X.; Chan, T. (2010). "Un marco general para una clase de algoritmos duales primarios de primer orden para la optimización convexa en la ciencia de la imagen". Revista SIAM de 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 51ª Conferencia IEEE sobre Decisión y Control (CDC) . págs. 5110–5115. doi :10.1109/CDC.2012.6426141. ISBN 978-1-4673-2066-5. S2CID  12128421.
18. "Método de multiplicadores de dirección alterna: 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 lagrangianos prácticos aumentados para optimización restringida , Filadelfia: Sociedad de Matemática Industrial y Aplicada , 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