En el campo de la optimización matemática , la relajación lagrangiana es un método de relajación que se aproxima a 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 se puede resolver 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
Suponga que se nos da un problema de programación lineal , con y , de la siguiente forma:
max S t
Si dividimos las restricciones en tal que , y podemos escribir el sistema:
max S t (1) (2)
Podemos introducir la restricción (2) en el objetivo:
max S t (1)
Si dejamos ser pesos no negativos, nos penalizan si violamos la restricción (2), y también somos recompensados si satisfacemos la restricción estrictamente. El sistema anterior se denomina relajación lagrangiana de nuestro problema original.
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 de Lagrange no será menor que el resultado óptimo del problema original. Para ver esto, deja ser la solución óptima al problema original, y dejar ser la solución óptima para la relajación lagrangiana. Entonces podemos ver que
La primera desigualdad es verdadera porque es factible en el problema original y la segunda desigualdad es verdadera porque es la solución óptima para la relajación lagrangiana.
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.
min S t
donde definimos como
max S t (1)
Por tanto, un algoritmo de relajación de Lagrange procede a explorar el rango de valores mientras se busca minimizar el resultado devuelto por el interior problema. Cada valor devuelto pores un límite superior candidato al 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 el 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 la tolerancia deseada.
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. Se introdujo en la década de 1970 y se ha utilizado ampliamente.
El método de penalización no utiliza variables duales, sino que elimina las restricciones y, en su lugar, penaliza las desviaciones de la restricción. El método es conceptualmente simple, pero generalmente se prefieren los métodos lagrangianos aumentados en la práctica, ya que el método de penalización adolece de problemas de acondicionamiento.
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.CS1 maint: varios nombres: lista de autores ( enlace )
- Bertsekas, Dimitri P. (1999). Programación no lineal: 2ª edición. Athena Scientific. 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 análisis y minimización convexos, Volumen I: Fundamentos . Grundlehren der Mathematischen Wissenschaften [Principios fundamentales de las ciencias matemáticas]. 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 practicantes". Algoritmos de análisis y minimización convexos, Volumen II: Teoría avanzada y métodos de agrupación . Grundlehren der Mathematischen Wissenschaften [Principios fundamentales de las ciencias matemáticas]. 306 . Berlín: Springer-Verlag. págs. xviii + 346. ISBN 3-540-56852-2.
- Lasdon, Leon S. (2002). Teoría de la optimización para grandes sistemas (reimpresión de la edición de 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 en Ciencias de la Computación. 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 .
- 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. Señor 0868279 . (2008 Segunda ed., En francés: Programmation mathématique: Théorie et algorítmes . Ediciones Tec & Doc, París, 2008. xxx + 711 pp.).
Artículos
- Everett, Hugh, III (1963). "Método multiplicador de Lagrange generalizado para la resolución de problemas de asignación óptima de recursos". Investigación operativa . 11 (3): 399–417. doi : 10.1287 / opre.11.3.399 . JSTOR 168028 . Señor 0152360 .
- Kiwiel, Krzysztof C .; Larsson, Torbjörn; Lindberg, P. O. (agosto de 2007). "Relajación lagrangiana a través de métodos de subgradiente ballstep". Matemáticas de la investigación operativa . 32 (3): 669–686. doi : 10.1287 / moor.1070.0261 . Señor 2348241 .
- Bragin, Mikhail A .; Luh, Peter B .; Yan, Joseph H .; Yu, Nanpeng y Stern, Gary A. (2015). "Convergencia del método de relajación lagrangiano sustituto", Revista de teoría y aplicaciones de optimización. 164 (1): 173-201, doi: 10.1007 / s10957-014-0561-3