Hispanopedia Wiki
Articulo de referencia

Método de Lagrangiano aumentado

Los métodos de Lagrangiano aumentado son una clase de algoritmos para resolver problemas de optimización con restricciones . Se asemejan a los métodos de penalización en que ree...

Hispanopedia WikiContenido en espanolLectura gratuita

Los métodos de Lagrangiano aumentado son una clase de algoritmos para resolver problemas de optimización con restricciones . Se asemejan a los métodos de penalización en 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 a la función objetivo ; sin embargo, el método de Lagrangiano aumentado añade otro término diseñado para imitar un multiplicador de Lagrange . El método de 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 con restricciones, con un término de penalización adicional (el aumento ).

El método se conocía originalmente como el método de los multiplicadores y se estudió en las décadas de 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 la 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 los multiplicadores", que maneja restricciones de desigualdad con una función lagrangiana aumentada dos veces diferenciable.

Desde la década de 1970, la programación cuadrática secuencial (SQP) y los métodos de punto interior (IPM) han recibido mayor atención, en parte porque utilizan más fácilmente subrutinas de matrices dispersas de bibliotecas de software numérico , y en parte porque los IPM poseen resultados de complejidad comprobados a través de la teoría de funciones autoconcordantes . El método del lagrangiano aumentado fue revitalizado 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 ]

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

Método general

Consideremos la resolución del siguiente problema de optimización con restricciones:

minF(incógnita){\displaystyle \min f(\mathbf {x} )}

sujeto a

doi(incógnita)=0 ∀i∈mi,{\displaystyle c_{i}(\mathbf {x} )=0~\forall i\in {\mathcal {E}},}

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

minΦk(incógnita)=F(incógnita)+μk ∑i∈mi doi(incógnita)2.{\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, luego en la siguiente iteración vuelve a resolver el problema utilizando un valor mayor deμk{\displaystyle \mu _{k}}y utilizando la solución anterior como estimación inicial o "punto de partida en caliente".

El método del lagrangiano aumentado utiliza la siguiente función objetivo sin restricciones:

minΦk(incógnita)=F(incógnita)+μk2 ∑i∈mi doi(incógnita)2+∑i∈mi λidoi(incógnita){\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 actualizarμk{\displaystyle \mu _{k}}, la variableλ{\displaystyle \lambda }También se actualiza según la regla.

λi←λi+μkdoi(incógnitak){\displaystyle \lambda _{i}\leftarrow \lambda _{i}+\mu _{k}c_{i}(\mathbf {x} _{k})}

dóndeincógnitak{\displaystyle \mathbf {x} _{k}}es la solución al problema sin restricciones en el k -ésimo paso (es decir,incógnitak=argininaΦk(incógnita){\displaystyle \mathbf {x} _{k}={\text{argmin}}\Phi _{k}(\mathbf {x} )}).

La variableλ{\displaystyle \lambda }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μ→∞{\displaystyle \mu \rightarrow \infty }para resolver el problema original con restricciones. Debido a la presencia del término multiplicador de Lagrange,μ{\displaystyle \mu }pueden permanecer mucho más pequeños, evitando así el mal condicionamiento. [ 6 ] Sin embargo, en las implementaciones prácticas es común proyectar estimaciones de multiplicadores en un conjunto acotado grande (salvaguardas) que evita inestabilidades numéricas y conduce a una fuerte convergencia teórica. [ 5 ]

El método puede extenderse para manejar restricciones de desigualdad. Para un análisis de mejoras prácticas, véanse las referencias [ 6 ] [ 5 ].

Método de direcciones alternas de multiplicadores

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

minincógnitaF(incógnita)+gramo(METROincógnita).{\displaystyle \min _{x}f(x)+g(Mx).}

Esto es equivalente al problema restringido,

minincógnita,yF(incógnita)+gramo(y),sujeto aMETROincógnita=y.{\displaystyle \min _{x,y}f(x)+g(y),\quad {\text{sujeto a}}\quad Mx=y.}

Aunque este cambio pueda parecer trivial, el problema ahora puede abordarse utilizando métodos de optimización con restricciones (en particular, el método del 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 resolver este problema de forma aproximada resolviendo primero x con y fijo y luego y con x fijo. En lugar de iterar este proceso hasta la convergencia (como el método de Jacobi ), el algoritmo ADMM 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 ciertas suposiciones. Debido a que no minimiza ni minimiza aproximadamente el lagrangiano aumentado, el algoritmo es distinto del método del lagrangiano aumentado ordinario.

El ADMM puede considerarse una aplicación del algoritmo de división de Douglas-Rachford , y este último, a su vez, es una instancia del algoritmo del punto proximal ; para más detalles, véase la referencia [ 7 ] . Existen varios paquetes de software modernos, como YALL1 [ 8 ] (2009), SpaRSA [ 9 ] (2009) y SALSA [ 10 ] (2009), que resuelven problemas de búsqueda de base y sus variantes, y utilizan el ADMM. También hay paquetes que emplean el ADMM para resolver problemas más generales, algunos de los cuales pueden aprovechar 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 del gradiente de la función. El objetivo es obtener una estimación del parámetro óptimo (minimizador) para cada nueva muestra. Con algunas modificaciones, ADMM puede utilizarse para la optimización estocástica. En un entorno estocástico, solo se tiene acceso a muestras ruidosas del gradiente, por lo que se utiliza una aproximación inexacta del lagrangiano.

L^ρ,k=F1(incógnitak)+⟨∇F(incógnitak,ζk+1),incógnita⟩+gramo(y)−zT(Aincógnita+By−do)+ρ2‖Aincógnita+By−do‖2+‖incógnita−incógnitak‖22ηk+1,{\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}}},}

dóndeηk+1{\displaystyle \eta _{k+1}}es un tamaño de paso que varía con el tiempo. [ 13 ]

ADMM se ha aplicado para resolver problemas regularizados, donde la optimización y regularización de la función se pueden llevar a cabo 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 dimensionalidad, ya que la regularización es un mecanismo natural para superar la malposición y fomentar la parsimonia en la solución óptima (por ejemplo, escasez y bajo rango). La eficacia de ADMM para resolver problemas regularizados podría implicar su utilidad para resolver problemas de optimización estocástica de alta dimensionalidad.

Enfoques alternativos

Software

Implementaciones de código abierto y no gratuitas/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 precondicionado)
  • PENNON (GPL 3, licencia comercial disponible)
  • LANCELOT (licencia gratuita para "uso interno", opciones comerciales de pago)
  • MINOS (también utiliza un método lagrangiano aumentado para algunos tipos de problemas).
  • El código de REASON, con licencia Apache 2.0 , está disponible en línea. [ 18 ]
  • ALGENCAN (implementación en Fortran del método lagrangiano aumentado con medidas de seguridad). Disponible en línea. [ 19 ]
  • NLOPT (implementación en C++ del optimizador lagrangiano aumentado, accesible desde diferentes lenguajes de programación [ 20 ] [ 21 ] ) [ 22 ]
  • PyProximal (implementación en Python del método del lagrangiano aumentado). [ 23 ]

Véase también

Referencias

  1. ↑ Hestenes, MR (1969). "Métodos de multiplicadores y gradientes". Journal of Optimization Theory and Applications . 4 (5): 303– 320. doi : 10.1007/BF00927673 .
  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. pp. 283–298 . ISBN  0-12-260650-7.
  3. ↑ Bertsekas, Dimitri P. (1982). Optimización con restricciones y métodos de multiplicadores de Lagrange . doi : 10.1016/C2013-0-10366-2 . ISBN 978-0-12-093480-5.
  4. ↑ Andreani, R.; Birgin, EG; Martínez, JM; Schuverdt, ML (enero de 2008). "Sobre métodos lagrangianos aumentados con restricciones generales de nivel inferior". SIAM Journal on Optimization . 18 (4): 1286– 1309. doi : 10.1137/060654797 .
  5. 1 2 3 Birgin y Martínez (2014)
  6. 1 2 3 Nocedal y Wright (2006) , capítulo 17
  7. ↑ Eckstein, Jonathan; Bertsekas, Dimitri P. (abril de 1992). "Sobre el método de división de Douglas-Rachford y el algoritmo de punto proximal para operadores monótonos maximales". Mathematical Programming . 55 ( 1–3 ): 293–318 . doi : 10.1007/BF01581204 . hdl : 1721.1/3160 .
  8. ↑ "YALL1: Tus 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, Hua; He, Niao; Tran, Long; Gray, Alexander (13 de febrero de 2013). Método estocástico de direcciones alternas de multiplicadores . Actas de la 30.ª Conferencia Internacional sobre Aprendizaje Automático. PMLR. págs. 80–88 . 
  14. ↑ Boyd, Stephen (2010). "Optimización distribuida y aprendizaje estadístico mediante el método de multiplicadores de dirección alternada". Foundations and Trends in Machine Learning . 3 (1): 1– 122. doi : 10.1561/2200000016 .
  15. ↑ Wahlberg, Bo; Boyd, Stephen; Annergren, Mariette; Wang, Yang (julio de 2012). "Un algoritmo ADMM para una clase de problemas de estimación regularizados de variación total". IFAC Proceedings Volumes . 45 (16): 83– 88. arXiv : 1203.1828 . doi : 10.3182/20120711-3-BE-2027.00310 .
  16. ↑ Esser, E.; Zhang, X.; Chan, T. (2010). "Un marco general para una clase de algoritmos primales-duales de primer orden para la optimización convexa en la ciencia de la imagen". SIAM Journal on Imaging Sciences . 3 (4): 1015– 1046. doi : 10.1137/09076934X .
  17. ↑ Mota, Joao FC; Xavier, Joao MF; Aguiar, Pedro MQ; Puschel, Markus (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.
  18. ↑ "Bitbucket" . bitbucket.org .
  19. ↑ " Proyecto TANGO" . www.ime.usp.br.
  20. ↑ Stamm, Aymeric (15-07-2022), nloptr , consultado el 19-07-2022
  21. ↑ El módulo NLopt para Julia , JuliaOpt, 25/06/2022 , consultado el 19/07/2022.
  22. ↑ Johnson, Steven G. (14 de julio de 2022), stevengj/nlopt , consultado el 19 de julio de 2022
  23. ↑ "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 lagrangiano aumentado para optimización con restricciones , 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