Hispanopedia Wiki
Articulo de referencia

Relajación (aproximación)

En optimización matemática y campos afines, la relajación es una estrategia de modelado . Una relajación consiste en aproximar un problema complejo mediante un problema cercano ...

Hispanopedia WikiContenido en espanolLectura gratuita

En optimización matemática y campos afines, la relajación es una estrategia de modelado . Una relajación consiste en aproximar un problema complejo mediante un problema cercano más fácil de resolver. La 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 complejo en optimización combinatoria penaliza las violaciones de algunas restricciones, lo que permite resolver un problema relajado más sencillo. Las técnicas de relajación complementan o refuerzan los algoritmos de ramificación y acotación de la optimización combinatoria; las relajaciones de programación lineal y lagrangiana se utilizan para obtener cotas 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

z=min{do(incógnita):incógnita∈incógnita⊆Rnorte}{\displaystyle z=\min\{c(x):x\in X\subseteq \mathbf {R} ^{n}\}}

es otro problema de minimización de la forma

zR=min{doR(incógnita):incógnita∈incógnitaR⊆Rnorte}{\displaystyle z_{R}=\min\{c_{R}(x):x\in X_{R}\subseteq \mathbf {R} ^{n}\}}

con estas dos propiedades

  1. incógnitaR⊇incógnita{\displaystyle X_{R}\supseteq X}
  2. doR(incógnita)≤do(incógnita){\displaystyle c_{R}(x)\leq c(x)}a pesar deincógnita∈incógnita{\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

Siincógnita∗{\displaystyle x^{*}}es una solución óptima del problema original, entoncesincógnita∗∈incógnita⊆incógnitaR{\displaystyle x^{*}\in X\subseteteq X_{R}}yz=do(incógnita∗)≥doR(incógnita∗)≥zR{\displaystyle z=c(x^{*})\geq c_{R}(x^{*})\geq z_{R}}. Por lo tanto,incógnita∗∈incógnitaR{\displaystyle x^{*}\in X_{R}}proporciona un límite superior enzR{\displaystyle z_{R}}.

Si además de los supuestos anteriores,doR(incógnita)=do(incógnita){\displaystyle c_{R}(x)=c(x)},∀incógnita∈incógnita{\displaystyle \forall x\in X}, 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 ]

Algunas técnicas de relajación

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. 1 2 3 Geoffrion (1971)
  2. 1 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. Notes in Math. 207. Harlow: Longmann.
  • Geoffrion, AM (1971). "Dualidad en programación no lineal: un desarrollo simplificado orientado a aplicaciones". SIAM Review . 13 (1): 1– 37. doi : 10.1137/1013001 . JSTOR 2028848 . 
  • Goffin, J.-L. (1980). "El método de relajación para resolver sistemas de desigualdades lineales". Matemáticas de la Investigación Operativa . 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: Publicación de Wiley-Interscience. 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-9MR 0720547 .​ 
  • Nemhauser, GL ; Rinnooy Kan, AHG; Todd, MJ, eds. (1989). Optimización . Manuales de investigación operativa y ciencias de la gestión. Vol.  1. Ámsterdam: North-Holland Publishing Co. ISBN 978-0-444-87284-5. MR 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 operativa . Prentice Hall. ISBN 978-0-02-398415-0.
  • Roubíček, T. (1997). Relaxation in Optimization Theory and Variational Calculus . Berlín: Walter de Gruyter. ISBN 978-3-11-014542-7.