Brecha de dualidad

La brecha de dualidad es la diferencia entre las soluciones directa y dual . Si es el valor óptimo del problema dual y es el valor óptimo del problema directo, entonces la brecha de dualidad es . Este valor siempre es mayor o igual a cero (para problemas de minimización). La brecha de dualidad es cero si y solo si hay una fuerte dualidad . De lo contrario, la discontinuidad es estrictamente positiva y se produce una dualidad débil [1] . ${\ estilo de visualización d^{*}}$ $p^{*}$ $p^{*}-d^{*}$

Descripción

En el caso general, sea dado el par dual espacios separados localmente convexos y . Entonces, dada una función , podemos definir el problema directo como ${\ estilo de visualización \ izquierda (X, X ^ {*} \ derecha)}$ ${\ estilo de visualización \ izquierda (Y, Y ^ {*} \ derecha)}$ ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \))$

{\ estilo de visualización \ inf _ {x \ en X} f (x). \,}

Si hay restricciones, se pueden incorporar a la función agregando una función de indicador en las restricciones — . Entonces sea una función de perturbación tal que . La brecha de dualidad es la diferencia, que viene dada por la fórmula $F$ $yo$ ${\ estilo de visualización f = f + yo}$ ${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \))$ ${\ estilo de visualización F (x, 0) = f (x)}$

\inf _{x\in X}[F(x,0)]-\sup_{y^{*}\in Y^{*}}[-F^{*}(0,y^ {*})]

donde es la función conjugada de ambas variables [2] [3] [4] . $F^{*}$

Alternativas

En la optimización computacional , se suele mencionar otra “brecha de dualidad”, que es la diferencia de valores entre cualquier solución y el valor de un valor admisible pero subóptimo del problema directo. Esta "brecha de dualidad" alternativa cuantifica la discrepancia entre el valor del valor actual factible pero subóptimo del problema directo y el valor del problema dual. El valor del problema dual, según las condiciones de regularidad, es igual al valor de la relajación convexa del problema directo. La relajación convexa es un problema que se obtiene reemplazando un conjunto no convexo de soluciones factibles con su envolvente convexa cerrada y reemplazando una función no convexa con su clausura convexa , es decir, con una función cuyo epígrafe es una envolvente convexa cerrada de la epígrafe de la función objetivo original del problema directo [5] [6 ] [7] [8] [9] [10] [11] [12] [13] .

Notas

↑ Borwein, Zhu, 2005 .
↑ Boţ, Wanka, Grad, 2009 .
↑ Csetnek, 2010 .
↑ Zălinescu, 2002 , pág. 106–113.
↑ Ahuja, Magnanti, Orlín, 1993 .
↑ Bertsekas, 1999 .
↑ Bonnans, Gilbert, Lemaréchal, Sagastizábal, 2006 , p. xiv+490.
↑ Hiriart-Urruty, Lemaréchal, 1993 , p. xviii+417.
↑ Hiriart-Urruty, Lemaréchal, 1993 , p. xviii+346.
↑ Lasdon, 2002 , pág. XIII+523.
↑ Lemarechal, 2001 , pág. 112–156.
↑ Minoux, 1986 , pág. xxviii+489.
↑ Shapiro, 1979 , pág. xvi+388.

Literatura

Jonathan Borwein, QijiZhu. Técnicas de Análisis Variacional. - Springer, 2005. - ISBN 978-1-4419-2026-3 .
Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Dualidad en Optimización de Vectores. - Springer, 2009. - ISBN 978-3-642-02885-4 .
Ernö Robert Csetnek. Superación del fallo de las condiciones de regularidad clásicas generalizadas del punto interior en la optimización convexa. Aplicaciones de la teoría de la dualidad a ampliaciones de operadores monótonos máximos. - Logos Verlag Berlin GmbH, 2010. - ISBN 978-3-8325-2503-3 .
Zălinescu C. Análisis convexo en espacios vectoriales generales. — River Edge, Nueva Jersey: World Scientific Publishing Co. Inc, 2002. - ISBN 981-238-067-1 .
Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Flujos de Red: Teoría, Algoritmos y Aplicaciones. - Prentice Hall, 1993. - ISBN 0-13-617549-X .
Dimitri P. Bertsekas. programación no lineal. — 2do. - Athena Scientific, 1999. - ISBN 1-886529-00-0 .
J. Fredéric Bonnans, J. Charles Gilbert, Claude Lemaréchal, Claudia A. Sagastizábal. Optimización numérica: Aspectos teóricos y prácticos . — Segunda ed. revisada. de traducción de 1997 francés. - Berlín: Springer-Verlag, 2006. - (Universitex). — ISBN 3-540-35445-X . -doi : 10.1007 / 978-3-540-35447-5 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Algoritmos de minimización y análisis convexo, Volumen I: Fundamentos. - Berlín: Springer-Verlag, 1993. - V. 305. - (Grundlehren der Mathematischen Wissenschaften [Principios fundamentales de las ciencias matemáticas]). — ISBN 3-540-56850-6 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. XII. Dualidad abstracta para profesionales // Análisis convexo y algoritmos de minimización, Volumen II: Teoría avanzada y métodos de paquetes. - Berlín: Springer-Verlag, 1993. - V. 306. - (Grundlehren der Mathematischen Wissenschaften [Principios fundamentales de las ciencias matemáticas]). — ISBN 3-540-56852-2 . -doi : 10.1007/ 978-3-662-06409-2_4 .
León S Lasdón. Teoría de optimización para grandes sistemas . - Mineola, Nueva York: Dover Publications, Inc., 2002. - ISBN 978-0-486-41999-2 .
Claude Lemarechal. Relajación lagrangiana // Optimización combinatoria computacional: artículos de la Spring School celebrada en Schloß Dagstuhl, del 15 al 19 de mayo de 2000 / Michael Jünger, Denis Naddef. - Berlín: Springer-Verlag, 2001. - T. 2241. - (Lecture Notes in Computer Science (LNCS)). — ISBN 3-540-42877-1 . -doi : 10.1007/ 3-540-45586-8_4 .
Michel Minoux. Programación matemática: Teoría y algoritmos / Egon Balas (adelante); Steven Vajda (trans) de (1983 París: Dunod). - Chichester: una publicación de Wiley-Interscience. John Wiley & Sons, Ltd., 1986. - ISBN 0-471-90170-9 . traducción de libros
- Programación matemática: teoría y algoritmos. — 2do. - París: Tec & Doc, 2008. - Pág. xxx+711 págs. - ISBN 978-2-7430-1000-3 .
Jeremy F. Shapiro. Programación matemática: Estructuras y algoritmos . - Nueva York: Wiley-Interscience [John Wiley & Sons], 1979. - ISBN 0-471-77886-9 .