Relajación (aproximación)

En optimización matemática y campos relacionados, la relajación es una estrategia de modelado . Una relajación es una aproximación de un problema difícil a un problema cercano que es más fácil de resolver. Una solución del problema relajado proporciona información sobre el problema original.

Por ejemplo, una relajación de la programación lineal de un problema de programación entera elimina la restricción de integralidad y, por lo tanto, permite soluciones racionales no enteras. Una relajación lagrangiana de un problema complicado en optimización combinatoria penaliza las violaciones de algunas restricciones, permitiendo resolver un problema relajado más fácil. Las técnicas de relajación complementan o suplementan los algoritmos de optimización combinatoria ramificados y ligados ; La programación lineal y las relajaciones lagrangianas se utilizan para obtener límites en algoritmos de rama y límite para programación de enteros. ^[1]

La estrategia de modelado de relajación no debe confundirse con los métodos iterativos de relajación , como la sobrerelajación sucesiva (SOR); Los métodos iterativos de relajación se utilizan para resolver problemas de ecuaciones diferenciales , mínimos cuadrados lineales y programación lineal . ^{[2] [3] [4]} Sin embargo, se han utilizado métodos iterativos de relajación para resolver relajaciones lagrangianas. ^[a]

Definición

Una relajación del problema de minimización.

${\displaystyle z=\min\{c(x):x\in X\subseteq \mathbf {R} ^{n}\}}$

es otro problema de minimización de la forma

${\displaystyle z_{R}=\min\{c_{R}(x):x\in X_{R}\subseteq \mathbf {R} ^{n}\}}$

con estas dos propiedades

1. ${\displaystyle X_{R}\supseteq X}$
2. ${\displaystyle c_{R}(x)\leq c(x)}$para todos . ${\displaystyle x\in X}$

La primera propiedad establece que el dominio factible del problema original es un subconjunto del dominio factible del problema relajado. La segunda propiedad establece que la función objetivo del problema original es mayor o igual que la función objetivo del problema relajado. ^[1]

Propiedades

Si es una solución óptima del problema original, entonces y . Por lo tanto, proporciona un límite superior para . ${\displaystyle x^{*}}$ ${\displaystyle x^{*}\in X\subseteq X_{R}}$ ${\displaystyle z=c(x^{*})\geq c_{R}(x^{*})\geq z_{R}}$ ${\displaystyle x^{*}\in X_{R}}$ ${\displaystyle z_{R}}$

Si además de los supuestos anteriores, , , se cumple lo siguiente: Si una solución óptima para el problema relajado es factible para el problema original, entonces es óptima para el problema original. ^[1] ${\displaystyle c_{R}(x)=c(x)}$ ${\displaystyle \forall x\in X}$

Algunas técnicas de relajación

• Relajación de la programación lineal
• relajación lagrangiana
• Relajación semidefinida
• Relajación sustituta y dualidad

Notas

1. Los métodos de relajación para encontrar soluciones factibles a sistemas de desigualdad lineal surgen en la programación lineal y en la relajación lagrangiana. ^{[2] [5] [6] [7] [8]}

1. Geoffrion (1971)
2. Goffin (1980).
3. Murty (1983), págs. 453–464.
4. Minoux (1986).
5. Minoux (1986), sección 4.3.7, págs. 120-123.
6. Shmuel Agmon (1954)
7. Theodore Motzkin e Isaac Schoenberg (1954)
8. LT Gubin, Boris T. Polyak y EV Raik (1969)

Referencias

• Buttazzo, G. (1989). Semicontinuidad, Relajación y Representación Integral en el Cálculo de Variaciones . Pitman Res. Apuntes en Matemáticas. 207. Harlow: Longmann.
• Geoffrion, AM (1971). "Dualidad en programación no lineal: un desarrollo simplificado orientado a aplicaciones". Revisión SIAM . 13 (1): 1–37. JSTOR  2028848.
• Goffin, J.-L. (1980). "El método de relajación para la resolución de sistemas de desigualdades lineales". Matemáticas de la Investigación de Operaciones . 5 (3): 388–414. doi :10.1287/moor.5.3.388. JSTOR  3689446. SEÑOR  0594854.
• Minoux, M. (1986). Programación matemática: Teoría y algoritmos . Chichester: una publicación de Wiley-Interscience. John Wiley e hijos. ISBN 978-0-471-90170-9. SEÑOR  0868279.Traducido por Steven Vajda de Programmation mathématique: Théorie et algoritmes . París: Dunod. 1983. SEÑOR  2571910.
• Murty, Katta G. (1983). "16 métodos iterativos para desigualdades lineales y programas lineales (especialmente 16.2 métodos de relajación y 16.4 algoritmos SOR iterativos que preservan la dispersión para programación lineal)". Programación lineal . Nueva York: John Wiley & Sons. ISBN 978-0-471-09725-9. SEÑOR  0720547.
• Nemhauser, GL ; Rinnooy Kan, AHG; Todd, MJ, eds. (1989). Optimización . Manuales de investigación de operaciones y ciencias de la gestión. vol. 1. Ámsterdam: North-Holland Publishing Co. ISBN 978-0-444-87284-5. SEÑOR  1105099.
  • WR Pulleyblank , Combinatoria poliédrica (págs. 371–446);
  • George L. Nemhauser y Laurence A. Wolsey, Programación entera (págs. 447–527);
  • Claude Lemaréchal , Optimización no diferenciable (págs. 529–572);
• Rardin, Ronald L. (1998). Optimización en la investigación de operaciones . Prentice Hall. ISBN 978-0-02-398415-0.
• Roubíček, T. (1997). Relajación en Teoría de la Optimización y Cálculo Variacional . Berlín: Walter de Gruyter. ISBN 978-3-11-014542-7.