Relajación (aproximación)

En la 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 mediante 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 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, lo que permite resolver un problema relajado más fácil. Las técnicas de relajación complementan o suplementan los algoritmos de ramificación y acotación de optimización combinatoria; la programación lineal y las relajaciones lagrangianas se utilizan para obtener acotaciones en algoritmos de ramificación y acotación para programación entera. ^[1]

La estrategia de modelado de relajación no debe confundirse con los métodos iterativos de relajación , como la sobre-relajación sucesiva (SOR); los métodos iterativos de relajación se utilizan para resolver problemas en ecuaciones diferenciales , mínimos cuadrados lineales y programación lineal . ^{[2] [3] [4]} Sin embargo, los métodos iterativos de relajación se han utilizado 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 programación lineal
• Relajación lagrangiana
• Relajación semidefinida
• Relajación sustitutiva y dualidad

Notas

1. Los métodos de relajación para encontrar soluciones factibles a sistemas de desigualdades lineales 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. Notas de matemáticas. 207. Harlow: Longmann.
• Geoffrion, AM (1971). "Dualidad en programación no lineal: un desarrollo simplificado orientado a aplicaciones". SIAM Review . 13 (1): 1–37. JSTOR  2028848.
• Goffin, J.-L. (1980). "El método de relajación para resolver 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. MR  0594854.
• Minoux, M. (1986). Programación matemática: teoría y algoritmos . Chichester: A Wiley-Interscience Publication. John Wiley & Sons. ISBN 978-0-471-90170-9.Sr. 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 escasez para programación lineal)". Programación lineal . Nueva York: John Wiley & Sons. ISBN 978-0-471-09725-9.Sr. 0720547  .
• Nemhauser, GL ; Rinnooy Kan, AHG; Todd, MJ, eds. (1989). Optimización . Manuales de investigación de operaciones y ciencia 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 la teoría de optimización y el cálculo variacional . Berlín: Walter de Gruyter. ISBN 978-3-11-014542-7.