relajación lagrangiana

En el campo de la optimización matemática , la relajación lagrangiana es un método de relajación que aproxima un problema difícil de optimización restringida mediante un problema más simple. Una solución al problema relajado es una solución aproximada al problema original y proporciona información útil.

El método penaliza las violaciones de las restricciones de desigualdad utilizando un multiplicador de Lagrange , que impone un costo a las violaciones. Estos costos adicionales se utilizan en lugar de las estrictas restricciones de desigualdad en la optimización. En la práctica, este problema relajado a menudo puede resolverse más fácilmente que el problema original.

El problema de maximizar la función lagrangiana de las variables duales (los multiplicadores lagrangianos) es el problema dual lagrangiano .

Descripción matemática

Supongamos que se nos da un problema de programación lineal , con y , de la siguiente forma: ${\displaystyle x\in \mathbb {R} ^{n}}$ ${\displaystyle A\in \mathbb {R} ^{m,n}}$

Si dividimos las restricciones de tal manera que , podemos escribir el sistema: ${\displaystyle A}$ ${\displaystyle A_{1}\in \mathbb {R} ^{m_{1},n}}$ ${\displaystyle A_{2}\in \mathbb {R} ^{m_{2},n}}$ ${\displaystyle m_{1}+m_{2}=m}$

Podemos introducir la restricción (2) en el objetivo:

Si permitimos pesos no negativos, seremos penalizados si violamos la restricción (2), y también seremos recompensados ​​si cumplimos estrictamente la restricción. El sistema anterior se llama relajación lagrangiana de nuestro problema original. ${\displaystyle \lambda =(\lambda _{1},\ldots ,\lambda _{m_{2}})}$

La solución LR como límite.

De particular utilidad es la propiedad de que para cualquier conjunto fijo de valores, el resultado óptimo del problema de relajación lagrangiano no será menor que el resultado óptimo del problema original. Para ver esto, sea la solución óptima al problema original y sea la solución óptima a la relajación lagrangiana. Entonces podemos ver que ${\displaystyle {\tilde {\lambda }}\succeq 0}$ ${\displaystyle {\hat {x}}}$ ${\displaystyle {\bar {x}}}$

La primera desigualdad es verdadera porque es factible en el problema original y la segunda desigualdad es verdadera porque es la solución óptima a la relajación lagrangiana. ${\displaystyle {\hat {x}}}$ ${\displaystyle {\bar {x}}}$

Iterando hacia una solución del problema original.

La desigualdad anterior nos dice que si minimizamos el valor máximo que obtenemos del problema relajado, obtenemos un límite más estricto en el valor objetivo de nuestro problema original. Por lo tanto, podemos abordar el problema original explorando en su lugar el problema parcialmente dualizado.

donde definimos como ${\displaystyle P(\lambda )}$

Por tanto, un algoritmo de relajación lagrangiano procede a explorar el rango de valores factibles mientras busca minimizar el resultado devuelto por el problema interno. Cada valor devuelto por es un límite superior candidato para el problema, el más pequeño de los cuales se mantiene como el mejor límite superior. Si además empleamos una heurística, probablemente sembrada por los valores devueltos por , para encontrar soluciones factibles al problema original, entonces podemos iterar hasta que el mejor límite superior y el costo de la mejor solución factible converjan a una tolerancia deseada. ${\displaystyle \lambda }$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle {\bar {x}}}$ ${\displaystyle P}$

Métodos relacionados

El método lagrangiano aumentado es bastante similar en espíritu al método de relajación lagrangiano, pero agrega un término adicional y actualiza los parámetros duales de una manera más basada en principios. Fue introducido en la década de 1970 y se ha utilizado ampliamente. ${\displaystyle \lambda }$

El método de penalización no utiliza variables duales, sino que elimina las restricciones y, en cambio, penaliza las desviaciones de la restricción. El método es conceptualmente simple, pero en la práctica generalmente se prefieren los métodos lagrangianos aumentados, ya que el método de penalización adolece de problemas de mal condicionamiento.

Referencias

Libros

• Ravindra K. Ahuja , Thomas L. Magnanti y James B. Orlin (1993). Flujos de red: teoría, algoritmos y aplicaciones . Prentice Hall. ISBN 0-13-617549-X.{{cite book}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
• Bertsekas, Dimitri P. (1999). Programación no lineal: 2da edición. Atenas científica. ISBN 1-886529-00-0 . 
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Optimización numérica: Aspectos teóricos y prácticos. Universitext (Segunda edición revisada de la traducción de la edición francesa de 1997). Berlín: Springer-Verlag. págs. xiv+490. doi :10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. SEÑOR  2265882.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Algoritmos de minimización y análisis convexo, Volumen I: Fundamentos . Grundlehren der Mathematischen Wissenschaften [Principios fundamentales de las ciencias matemáticas]. vol. 305. Berlín: Springer-Verlag. págs. xviii+417. ISBN 3-540-56850-6. SEÑOR  1261420.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). "14 Dualidad para los profesionales". Algoritmos de minimización y análisis convexo, Volumen II: Teoría avanzada y métodos de paquetes . Grundlehren der Mathematischen Wissenschaften [Principios fundamentales de las ciencias matemáticas]. vol. 306. Berlín: Springer-Verlag. págs. xviii+346. ISBN 3-540-56852-2.
• Lasdon, León S. (2002). Teoría de optimización para sistemas grandes (reimpresión de la edición Macmillan de 1970). Mineola, Nueva York: Dover Publications, Inc. págs. xiii+523. SEÑOR  1888251.
• Lemaréchal, Claude (2001). "Relajación lagrangiana". En Michael Jünger y Denis Naddef (ed.). Optimización combinatoria computacional: artículos de la escuela de primavera celebrada en Schloß Dagstuhl, del 15 al 19 de mayo de 2000 . Apuntes de conferencias sobre informática. vol. 2241. Berlín: Springer-Verlag. págs. 112-156. doi :10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. SEÑOR  1900016. S2CID  9048698.
• Minoux, M. (1986). Programación matemática: Teoría y algoritmos . Egon Balas (prólogo) (Traducido por Steven Vajda de la edición francesa (1983 París: Dunod)). Chichester: una publicación de Wiley-Interscience. John Wiley & Sons, Ltd. págs. xxviii + 489. ISBN 0-471-90170-9. MR  0868279. (2008 Segunda ed., en francés: Programmation mathématique: Théorie et algoritmos . Ediciones Tec & Doc, París, 2008. xxx+711 págs.).

Artículos

• Everett, Hugo III (1963). "Método multiplicador de Lagrange generalizado para la resolución de problemas de asignación óptima de recursos". La investigación de operaciones . 11 (3): 399–417. doi :10.1287/opre.11.3.399. JSTOR  168028. SEÑOR  0152360.
• Kiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, PO (agosto de 2007). "Relajación lagrangiana mediante métodos de subgradiente de paso de bola". Matemáticas de la Investigación de Operaciones . 32 (3): 669–686. doi :10.1287/moor.1070.0261. SEÑOR  2348241.
• Bragin, Mikhail A.; Luh, Peter B.; Yan, José H.; Yu, Nanpeng y Stern, Gary A. (2015). "Convergencia del método de relajación lagrangiana sustituta", Revista de teoría y aplicaciones de optimización. 164 (1): 173-201, doi :10.1007/s10957-014-0561-3
• Bragin, Mikhail A.; Tucker, Emily, L. (2022) "Relajación lagrangiana sustituta" basada en niveles "para programación lineal entera mixta", Scientific Reports . 12 : 22417, doi:10.1038/s41598-022-26264-1
• Neal Young, Ejemplo de relajación lagrangiana, en el blog AlgNotes.
• Neal Young, 2012, Ejemplos de juguetes para solucionadores Plotkin-Shmoys-Tardos y Arora-Kale en CSTheory Stack Exchange.