En la teoría matemática de la optimización , la dualidad o el principio de dualidad es el principio de que los problemas de optimización pueden verse desde dos perspectivas, el problema primario o el problema dual . La solución al problema dual proporciona un límite inferior a la solución del problema primario (minimización). [1] Sin embargo, en general, los valores óptimos de los problemas primarios y duales no necesitan ser iguales. Su diferencia se llama brecha de dualidad . Para problemas de optimización convexa , la brecha de dualidad es cero bajo una condición de calificación de restricción .
Problema dual
Por lo general, el término "problema dual" se refiere al problema dual de Lagrange, pero se utilizan otros problemas duales, por ejemplo, el problema dual de Wolfe y el problema dual de Fenchel . El problema dual de Lagrange se obtiene formando el Lagrangiano de un problema de minimización mediante el uso de multiplicadores de Lagrange no negativos para sumar las restricciones a la función objetivo, y luego resolviendo los valores de las variables primarias que minimizan la función objetivo original. Esta solución da las variables primarias como funciones de los multiplicadores de Lagrange, que se denominan variables duales, de modo que el nuevo problema es maximizar la función objetivo con respecto a las variables duales bajo las restricciones derivadas sobre las variables duales (incluyendo al menos la no negatividad limitaciones).
En general, dados dos pares duales de espacios localmente convexos separados y y la función , podemos definir el problema primario como encontrar tal que En otras palabras, si existe es el mínimo de la funcióny se alcanza el mínimo (límite inferior más grande) de la función.
Si existen condiciones de restricción, estas se pueden integrar en la función Dejando dónde es una función adecuada en que tiene un mínimo de 0 en las restricciones, y para el cual se puede probar que . La última condición se satisface trivialmente, pero no siempre convenientemente, para la función característica (es decir, por satisfaciendo las limitaciones y de lo contrario). Luego extiendea una función de perturbación tal que . [2]
La brecha de dualidad es la diferencia de los lados derecho e izquierdo de la desigualdad.
dónde es el conjugado convexo en ambas variables ydenota el supremum (mínimo límite superior). [2] [3] [4]
Brecha de dualidad
La brecha de dualidad es la diferencia entre los valores de cualquier solución primaria y cualquier solución dual. Si es el valor dual óptimo y es el valor primario óptimo, entonces la brecha de dualidad es igual a . Este valor es siempre mayor o igual a 0. La brecha de dualidad es cero si y solo si se mantiene la dualidad fuerte . De lo contrario, la brecha es estrictamente positiva y la dualidad débil se mantiene. [5]
En la optimización computacional, a menudo se informa otra "brecha de dualidad", que es la diferencia de valor entre cualquier solución dual y el valor de una iteración factible pero subóptima para el problema primario. Esta "brecha de dualidad" alternativa cuantifica la discrepancia entre el valor de una iteración actual factible pero subóptima para el problema primario y el valor del problema dual; el valor del problema dual es, en condiciones de regularidad, igual al valor de la relajación convexa del problema primario: la relajación convexa es el problema que surge al reemplazar un conjunto factible no convexo con su casco convexo cerrado y al reemplazar un conjunto no convexo función convexa con su cierre convexo , que es la función que tiene el epígrafe que es el casco convexo cerrado de la función objetivo primordial original. [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16]
Caso lineal
Los problemas de programación lineal son problemas de optimización en los que la función objetivo y las restricciones son todas lineales . En el problema primario, la función objetivo es una combinación lineal de n variables. Hay m restricciones, cada una de las cuales coloca un límite superior en una combinación lineal de las n variables. El objetivo es maximizar el valor de la función objetivo sujeta a las restricciones. Una solución es un vector (una lista) de n valores que alcanza el valor máximo para la función objetivo.
En el problema dual, la función objetivo es una combinación lineal de los valores m que son los límites en las restricciones m del problema primario. Hay n restricciones duales, cada una de las cuales coloca un límite inferior en una combinación lineal de m variables duales.
Relación entre el problema primario y el problema dual
En el caso lineal, en el problema primario, desde cada punto subóptimo que satisface todas las restricciones, hay una dirección o subespacio de direcciones para moverse que aumenta la función objetivo. Se dice que moverse en cualquier dirección elimina la holgura entre la solución candidata y una o más restricciones. Un valor inviable de la solución candidata es uno que excede una o más de las restricciones.
En el problema dual, el vector dual multiplica las restricciones que determinan las posiciones de las restricciones en el primario. Variar el vector dual en el problema dual es equivalente a revisar los límites superiores en el problema primario. Se busca el límite superior más bajo. Es decir, el vector dual se minimiza para eliminar la holgura entre las posiciones candidatas de las restricciones y el óptimo real. Un valor inviable del vector dual es uno que es demasiado bajo. Establece las posiciones candidatas de una o más de las restricciones en una posición que excluye el óptimo real.
Esta intuición se formaliza mediante las ecuaciones en Programación lineal: Dualidad .
Caso no lineal
En la programación no lineal , las restricciones no son necesariamente lineales. No obstante, se aplican muchos de los mismos principios.
Para asegurar que el máximo global de un problema no lineal se pueda identificar fácilmente, la formulación del problema a menudo requiere que las funciones sean convexas y tengan conjuntos compactos de nivel inferior.
Este es el significado de las condiciones de Karush-Kuhn-Tucker . Proporcionan las condiciones necesarias para identificar óptimos locales de problemas de programación no lineal. Hay condiciones adicionales (calificaciones de restricción) que son necesarias para que sea posible definir la dirección hacia una solución óptima . Una solución óptima es aquella que es un óptimo local, pero posiblemente no un óptimo global.
El principio fuerte de Lagrange: la dualidad de Lagrange
Dado un problema de programación no lineal en forma estándar
con el dominio teniendo interior no vacío, la función lagrangiana Se define como
Los vectores y se denominan variables duales o vectores multiplicadores de Lagrange asociados con el problema. La función dual de Lagrange Se define como
La función dual g es cóncava, incluso cuando el problema inicial no es convexo, porque es un mínimo puntual de funciones afines. La función dual produce límites inferiores en el valor óptimodel problema inicial; para cualquier y cualquier tenemos .
Si se cumple una calificación de restricción como la condición de Slater y el problema original es convexo, entonces tenemos una fuerte dualidad , es decir.
Problemas convexos
Para un problema de minimización convexo con restricciones de desigualdad,
el problema dual de Lagrange es
donde la función objetivo es la función dual de Lagrange. Siempre que las funciones y son continuamente diferenciables, el mínimo se produce cuando el gradiente es igual a cero. El problema
se llama el problema dual de Wolfe. Este problema puede ser difícil de resolver computacionalmente, porque la función objetivo no es cóncava en las variables conjuntas.. Además, la restricción de igualdades no lineal en general, por lo que el problema dual de Wolfe suele ser un problema de optimización no convexo. En cualquier caso, la dualidad débil se mantiene. [17]
Historia
Según George Dantzig , el teorema de la dualidad para la optimización lineal fue conjeturado por John von Neumann inmediatamente después de que Dantzig presentara el problema de programación lineal. Von Neumann notó que estaba usando información de su teoría de juegos y conjeturó que el juego matricial de suma cero para dos personas era equivalente a la programación lineal. Albert W. Tucker y su grupo publicaron por primera vez pruebas rigurosas en 1948 . (Prólogo de Dantzig a Nering y Tucker, 1993)
Ver también
- Dualidad convexa
- Dualidad
- Relajación (aproximación)
Notas
- ^ Boyd, Stephen P .; Vandenberghe, Lieven (2004). Optimización convexa (pdf) . Prensa de la Universidad de Cambridge. pag. 216. ISBN 978-0-521-83378-3. Consultado el 15 de octubre de 2011 .
- ^ a b Boţ, Radu Ioan; Wanka, Gert; Grad, Sorin-Mihai (2009). Dualidad en la optimización vectorial . Saltador. ISBN 978-3-642-02885-4.
- ^ Csetnek, Ernö Robert (2010). Superar el fracaso de las condiciones clásicas de regularidad generalizada 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. ISBN 978-3-8325-2503-3.
- ^ Zălinescu, Constantin (2002). Análisis convexo en espacios vectoriales generales . River Edge, Nueva Jersey: World Scientific Publishing Co., Inc. pp. 106 -113. ISBN 981-238-067-1. Señor 1921556 .
- ^ Borwein, Jonathan; Zhu, Qiji (2005). Técnicas de análisis variacional . Saltador. ISBN 978-1-4419-2026-3.
- ^ Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Flujos de red: teoría, algoritmos y aplicaciones . Prentice Hall. ISBN 0-13-617549-X.
- ^ Bertsekas, Dimitri; Nedic, Angelia; Ozdaglar, Asuman (2003). Análisis y Optimización Convexos . Athena Scientific. ISBN 1-886529-45-0.
- ^ Bertsekas, Dimitri P. (1999). Programación no lineal (2ª ed.). Athena Scientific. ISBN 1-886529-00-0.
- ^ Bertsekas, Dimitri P. (2009). Teoría de la optimización convexa . Athena Scientific. ISBN 978-1-886529-31-1.
- ^ 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 combinados . 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. Señor 1295240 .
- ^ Lasdon, Leon S. (2002) [Reimpresión del Macmillan de 1970]. Teoría de optimización para grandes sistemas . Mineola, Nueva York: Dover Publications, Inc. págs. Xiii + 523. ISBN 978-0-486-41999-2. Señor 1888251 .
- ^ Lemaréchal, Claude (2001). "Relajación lagrangiana". En Jünger, Michael; Naddef, Denis (eds.). Optimización combinatoria computacional: artículos de la Escuela de Primavera celebrada en Schloß Dagstuhl, del 15 al 19 de mayo de 2000 . Lecture Notes in Computer Science (LNCS). 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, Michel (1986). Programación matemática: teoría y algoritmos . Egon Balas (delantero); Steven Vajda (traducción) del francés (1983 Paris: 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 , Éditions Tec & Doc, París, 2008. xxx + 711 pp.).
- ^ Shapiro, Jeremy F. (1979). Programación matemática: estructuras y algoritmos . Nueva York: Wiley-Interscience [John Wiley & Sons]. págs. xvi + 388 . ISBN 0-471-77886-9. Señor 0544669 .
- ^ Geoffrion, Arthur M. (1971). "Dualidad en programación no lineal: un desarrollo orientado a aplicaciones simplificado". Revisión SIAM . 13 (1): 1–37. doi : 10.1137 / 1013001 . JSTOR 2028848 .
Referencias
Libros
- Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Flujos de red: teoría, algoritmos y aplicaciones . Prentice Hall. ISBN 0-13-617549-X.
- Bertsekas, Dimitri; Nedic, Angelia; Ozdaglar, Asuman (2003). Análisis y Optimización Convexos . Athena Scientific. ISBN 1-886529-45-0.
- Bertsekas, Dimitri P. (1999). Programación no lineal (2ª ed.). Athena Scientific. ISBN 1-886529-00-0.
- Bertsekas, Dimitri P. (2009). Teoría de la optimización convexa . Athena Scientific. ISBN 978-1-886529-31-1.
- 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 .
- Cook, William J .; Cunningham, William H .; Pulleyblank, William R .; Schrijver, Alexander (12 de noviembre de 1997). Optimización combinatoria (1ª ed.). John Wiley e hijos. ISBN 0-471-55894-X.
- Dantzig, George B. (1963). Programación lineal y extensiones . Princeton, Nueva Jersey: Princeton University Press.
- 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 combinados . 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. Señor 1295240 .
- Lasdon, Leon S. (2002) [Reimpresión del Macmillan de 1970]. Teoría de optimización para grandes sistemas . Mineola, Nueva York: Dover Publications, Inc. págs. Xiii + 523. ISBN 978-0-486-41999-2. Señor 1888251 .
- Lawler, Eugene (2001). "4.5. Implicaciones combinatorias del teorema de corte mínimo de flujo máximo, 4.6. Interpretación de programación lineal del teorema de corte mínimo de flujo máximo". Optimización combinatoria: redes y matroides . Dover. págs. 117-120. ISBN 0-486-41453-1.
- Lemaréchal, Claude (2001). "Relajación lagrangiana". En Jünger, Michael; Naddef, Denis (eds.). Optimización combinatoria computacional: artículos de la Escuela de Primavera celebrada en Schloß Dagstuhl, del 15 al 19 de mayo de 2000 . Lecture Notes in Computer Science (LNCS). 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, Michel (1986). Programación matemática: teoría y algoritmos . Egon Balas (delantero); Steven Vajda (traducción) del francés (1983 Paris: 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 , Éditions Tec & Doc, París, 2008. xxx + 711 pp.)).
- Nering, Evar D .; Tucker, Albert W. (1993). Programación lineal y problemas relacionados . Boston, MA: Prensa académica. ISBN 978-0-12-515440-6.
- Papadimitriou, Christos H .; Steiglitz, Kenneth (julio de 1998). Optimización combinatoria: algoritmos y complejidad (edición íntegra). Dover. ISBN 0-486-40258-4.
- Ruszczyński, Andrzej (2006). Optimización no lineal . Princeton, Nueva Jersey: Princeton University Press . págs. xii + 454. ISBN 978-0691119151. Señor 2199043 .
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 . Archivado desde el original el 24 de julio de 2011.
- 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 .
- Dualidad en la programación lineal Gary D. Knott