Dualidad (optimización)

La dualidad , o principio de dualidad , es el principio por el cual los problemas de optimización pueden ser considerados desde dos puntos de vista, como un problema directo o como un problema dual . La solución del problema dual da la cota inferior del problema directo (al minimizar) [1] . Sin embargo, en el caso general, los valores de las funciones objetivo de las soluciones óptimas de los problemas directo y dual no necesariamente coinciden. La diferencia en estos valores, si se observa, se denomina brecha de dualidad . Para problemas de programación convexa , la brecha de dualidad es igual a cero cuando se cumplen las condiciones de regularidad de las restricciones .

Problema dual

Por lo general, el término "problema dual" implica el problema dual lagrangiano , pero también se utilizan otros problemas duales, como el problema dual de Wolfe y el problema dual de Fenchel . El problema de Lagrange dual se obtiene generando un Lagrangiano , usando multiplicadores de Lagrange no negativos para añadir restricciones a la función objetivo, y minimizando el Lagrangiano con respecto a algunas variables del problema directo. Tal solución da las variables del problema directo como funciones de multiplicadores de Lagrange, que se denominan variables duales, por lo que el nuevo problema se convierte en el problema de maximizar la función objetivo con respecto a las variables duales bajo las restricciones generadas sobre las variables duales ( al menos la no negatividad).

En general, dado el par dual [2] de un espacio convexo local separable y una función , podemos definir el problema directo como encontrar , tal que, en otras palabras, es el mínimo (límite inferior exacto) de la función . ${\ estilo de visualización \ izquierda (X, X ^ {*} \ derecha)}$ ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \))$ ${\ sombrero {x}}$ $f({\sombrero {x)))=\inf _{x\in X}f(x).\,$ ${\ estilo de visualización f ({\ sombrero {x)))}$ $F$

Si hay restricciones, se pueden incorporar a la función si ponemos , donde está la función indicadora . Sea ahora (para otro par dual ) una función de perturbación tal que [3] . $F$ ${\tilde {f}}=f+I_{\mathrm {restricciones} }$ $yo$ ${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \))$ ${\ estilo de visualización \ izquierda (Y, Y ^ {*} \ derecha)}$ $F(x,0)={\tilde {f))(x)$

La brecha de dualidad es la diferencia entre los lados derecho e izquierdo de la desigualdad

\sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leqslant \inf_{x\in X}F(x, 0),\,

donde es la función conjugada de ambas variables, y significa el supremo (límite superior exacto) [3] [4] [5] . $F^{*}$ $\arriba$

Brecha de dualidad

La brecha de dualidad es la diferencia entre los valores de cualquier solución al problema primario y los valores de cualquier solución al problema dual. Si es el valor óptimo del problema dual y es el valor óptimo del problema directo, la brecha de dualidad es . Este valor siempre es mayor o igual a 0. 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 [6] . ${\ estilo de visualización d^{*}}$ $p^{*}$ $p^{*}-d^{*}$

En los problemas de optimización numérica, a menudo se utiliza otra "brecha de dualidad", que es igual a la diferencia entre cualquier solución dual y el valor de una iteración admisible, pero no localmente óptima, para el problema directo. La alternativa "brecha de dualidad" expresa la discrepancia entre el valor de la solución factible actual, pero no localmente óptima, para el problema primario y el valor del problema dual. El valor del problema dual es igual, bajo la condición de regularidad de las restricciones, al valor del debilitamiento convexo del problema directo, donde el debilitamiento convexo surge como resultado de reemplazar el conjunto no convexo de soluciones factibles con su conjunto cerrado. casco convexo y reemplazando la función no convexa por su cierre convexo , es decir, con una función cuyo epígrafe es un convexo cerrado por cierre de la función objetivo original del problema directo [7] [8] [9] [10] [11 ] [12] [13] [14] [15] [16] [17] .

Caso lineal

Los problemas de programación lineal son problemas de optimización en los que la función objetivo y las restricciones son lineales. En el problema directo, la función objetivo es una combinación lineal de n variables. Hay m restricciones, cada una de las cuales limita la combinación lineal de n variables desde arriba. El objetivo es maximizar el valor de la función objetivo bajo restricciones. La solución es un vector (lista) de n valores que da el valor máximo de la función objetivo.

En el problema dual, la función objetivo es una combinación lineal de m valores que son los lados derechos de las m restricciones del problema primal. Hay n restricciones duales, cada una de las cuales limita una combinación lineal de m variables duales desde abajo.

Relación entre problemas primarios y duales

En el caso lineal, en el problema directo, desde cada punto del óptimo local que satisface todas las restricciones, existe una dirección o subespacio de direcciones, y el movimiento en esta dirección aumenta la función objetivo. Se dice que un movimiento en cualquiera de esas direcciones reduce la brecha entre una solución factible (o un plan factible ) y una de las restricciones. Una posible solución inválida es una solución que viola una o más restricciones.

En el problema dual, los elementos del vector dual se multiplican por columnas que corresponden a las restricciones del problema primal. La perturbación del vector dual en el problema dual es equivalente a revisar el límite superior del problema primal. Al resolver el problema dual, se busca el límite superior mínimo, es decir, el vector dual cambia de tal manera que se reduzca la brecha entre la solución factible y el óptimo real.

Para obtener más información sobre la conexión entre los problemas primal y dual, consulte el artículo " Problemas duales de programación lineal ".

Interpretación económica

Si entendemos nuestro problema de programación lineal primal como un problema clásico de "asignación de recursos", su problema dual puede interpretarse como un problema de " estimación de recursos " .

Caso no lineal

En la programación no lineal, las restricciones no son necesariamente lineales. Sin embargo, se aplican muchos de los principios del caso lineal.

Para garantizar que el máximo global de un problema no lineal se pueda definir fácilmente, el enunciado del problema a menudo requiere que las funciones sean convexas y tengan conjuntos compactos de niveles inferiores (es decir, conjuntos en los que la función toma un valor inferior a algún nivel). .

Esta es la condición de Karush-Kuhn-Tucker . Demostraron las condiciones necesarias para determinar el óptimo local de problemas no lineales. Hay condiciones adicionales (condición de regularidad de las restricciones) que son necesarias para determinar la dirección hacia la solución óptima . Aquí, la solución óptima es una de las óptimas locales, que pueden no ser globales.

Principio estricto de Lagrange: dualidad de Lagrange

Si un problema de programación no lineal se da en la forma estándar

minimizar	$f_{0}(x)$
bajo condiciones	${\displaystyle f_{i}(x)\leqslant 0,\i\in \left\{1,\dots,m\right\))$
	${\displaystyle h_{i}(x)=0,\ i\in \left\{1,\dots,p\right\))$

con dominio que tiene un interior no vacío, la función de Lagrange se define como ${\mathcal {D}}\subconjunto \mathbb {R} ^{n}$ $\Lambda:\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$

\Lambda (x,\lambda ,\nu )=f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\ suma_{i=1}^{p}\nu_{i}h_{i}(x).

Los vectores y se denominan variables duales o vectores de multiplicadores de Lagrange asociados al problema. La función dual de Lagrange se define como $\lambda$ $\nu$ $g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$

g(\lambda ,\nu )=\inf _{x\in {\mathcal {D))}\Lambda (x,\lambda ,\nu )=\inf _{x\in {\mathcal { D}}}\left(f_{0}(x)+\sum_{i=1}^{m}\lambda_{i}f_{i}(x)+\sum_{i=1}^ {p}\nu _{i}h_{i}(x)\derecha).

La función dual g es cóncava incluso si el problema inicial no es convexo, ya que es el mínimo puntual de las funciones afines. La función dual da cotas inferiores para el valor óptimo del problema original. Para cualquiera y cualquiera que tengamos . $p^{*}$ ${\ estilo de visualización \ lambda \ geqslant 0}$ $\nu$ $g(\lambda ,\nu )\leqslant p^{*}$

Si se cumplen las condiciones de regularidad de la restricción , como la condición de Slater , y el problema original es convexo, entonces tenemos dualidad estricta , es decir, . $d^{*}=\max_{\lambda \geqslant 0,\nu }g(\lambda ,\nu )=\inf f_{0}=p^{*}$

Problemas convexos

Para un problema de minimización convexo con restricciones - desigualdades,

minimizar	$f(x)$
bajo condiciones	$g_{i}(x)\leqslant 0,\quad i=1,\dots,m$

El problema dual lagrangiano es

maximizar	$\inf _{x}\left(f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\right)$
bajo condiciones	$u_{i}\geqslant 0,\quad i=1,\dots,m$

donde la función objetivo es la función dual de Lagrange. Si se sabe que las funciones y son continuamente diferenciables, entonces el mínimo está en los puntos donde el gradiente es cero. Una tarea $F$ ${\displaystyle g_{1},\cdots,g_{m))$

maximizar	$f(x)+\sum_{j=1}^{m}u_{j}g_{j}(x)$
bajo condiciones	$\nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)=0$
$u_{i}\geqslant 0,\quad i=1,\dots,m$

se llama el problema de Wolfe dual. Esta tarea puede ser computacionalmente difícil, ya que la función objetivo no es convexa en las coordenadas . Además, la restricción generalmente no es lineal, por lo que el problema de Wolfe dual suele ser un problema de optimización no convexo. En todo caso, existe una dualidad débil [18] . ${\ estilo de visualización (u, x)}$ $\nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)$

Historia

Según George Danzig , el teorema de la dualidad para la optimización lineal fue presentado como una conjetura por John von Neumann inmediatamente después de que Danzig introdujera el problema de programación lineal. Von Neumann notó que usó información de su teoría de juegos y sugirió que un juego matricial de suma cero de dos personas es equivalente a un problema de programación lineal. Una prueba rigurosa de este hecho fue publicada por primera vez en 1948 por Albert Tucker y su grupo [19] .

Véase también

Principio de dualidad
Atenuación (aproximación)

Notas

↑ Boyd, Vandenberghe, 2004 .
↑ El par dual es un triple , donde es un espacio vectorial sobre un campo , es el conjunto de todas las aplicaciones lineales , y el tercer elemento es una forma bilineal . $\left(X,X^{*},\langle ,\rangle \right)$ $X$ $F$ $X^{*}$ ${\ estilo de visualización \ phi \ dos puntos X \ a F}$ $X^{*}\times X\to F\colon (\phi ,x)\mapsto \phi (x)$
↑ 1 2 Boţ, Wanka, Grad., 2009 .
↑ Csetnek, 2010 .
↑ Zălinescu, 2002 , pág. 106–113.
↑ Borwein, Zhu, 2005 .
↑ Ahuja, Magnanti, Orlín, 1993 .
↑ Bertsekas, Nedic, Ozdaglar, 2003 .
↑ Bertsekas, 1999 .
↑ Bertsekas, 2009 .
↑ 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.
↑ Geoffrion, 1971 , pág. 1–37.
↑ Nering y Tucker 1993 , pág. prólogo de Danzig.

Literatura

Libros

Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Algoritmos de minimización y análisis convexo. Parte I: Fundamentos. - Berlín: Springer-Verlag, 1993. - T. 305. - S. xviii + 417. — (Grundlehren der Mathematischen Wissenschaften [Principios fundamentales de las ciencias matemáticas]). — ISBN 3-540-56850-6 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. 14 Dualidad para practicantes // Análisis convexo y algoritmos de minimización. Parte II: Teoría avanzada y métodos de paquetes. - Berlín: Springer-Verlag, 1993. - T. 306. - S. xviii + 346. — (Grundlehren der Mathematischen Wissenschaften [Principios fundamentales de las ciencias matemáticas]). — ISBN 3-540-56852-2 .
León S Lasdón. Teoría de optimización para grandes sistemas . - Mineola, Nueva York: Dover Publications, Inc., 2002. - Pág. xiii+523. — 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. - Berlín: Springer-Verlag, 2001. - Vol. 2241. - P. 112-156. - (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. - Chichester: una publicación de Wiley-Interscience. John Wiley & Sons, Ltd., 1986. - página xxviii+489. — ISBN 0-471-90170-9 .
- M. Minú. Programación matemática. Teoría y algoritmos.
Evar D. Nering, Albert W. Tucker. Programación Lineal y Problemas Relacionados . - Boston, MA: Academic Press, 1993. - ISBN 978-0-12-515440-6 .
Stephen P. Boyd, Lieven Vandenberghe. Optimización convexa . - Prensa de la Universidad de Cambridge, 2004. - ISBN 978-0-521-83378-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 .
Constantin Zalinescu. Análisis convexo en espacios vectoriales generales. — River Edge, NJ: World Scientific Publishing Co., Inc., 2002. — págs. 106–113. - 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 Bertsekas, Angelia Nedic, Asuman Ozdaglar. Análisis y Optimización Convexa. - Athena Scientific, 2003. - ISBN 1-886529-45-0 .
Dimitri P. Bertsekas. programación no lineal. — 2do. - Athena Scientific, 1999. - ISBN 1-886529-00-0 .
Dimitri P. Bertsekas. Teoría de la optimización convexa. - Athena Scientific, 2009. - ISBN 978-1-886529-31-1 .
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. - Berlín: Springer-Verlag, 2006. - p.xiv+490. — (Texto universitario). — ISBN 3-540-35445-X . -doi : 10.1007 / 978-3-540-35447-5 .
Jeremy F. Shapiro. Programación matemática: Estructuras y algoritmos . - Nueva York: Wiley-Interscience [John Wiley & Sons], 1979. - P. xvi + 388. — ISBN 0-471-77886-9 .
Jonathan Borwein, QijiZhu. Técnicas de Análisis Variacional. - Springer, 2005. - ISBN 978-1-4419-2026-3 .

Artículos

Dualidad en Programación Lineal Gary D. Knott
Arthur M. Geoffrion. Dualidad en la programación no lineal: un desarrollo simplificado orientado a aplicaciones // Revisión SIAM. - 1971. - T. 13 , núm. 1 . -doi : 10.1137/ 1013001 . — .

Lecturas adicionales

William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver. optimización combinatoria. — 1er. - John Wiley & Sons, 1997. - ISBN 0-471-55894-X .
Xugang Ye, Shih-Ping Han, Anhua Lin. Una nota sobre la conexión entre Primal-Dual y los algoritmos A* // International Journal of Operations Research and Information Systems. - 2010. - Vol. 1 , número. 1 . — págs. 73–85 .
George B. Dantzig. Programación Lineal y Extensiones. — Princeton, Nueva Jersey: Princeton University Press, 1963.
Eugenio Lawler. 4.5. Implicaciones combinatorias del teorema de corte mínimo de flujo máximo 4.6. Interpretación en Programación Lineal del Teorema de Corte Mínimo de Flujo Máximo // Optimización Combinatoria: Redes y Matroides. - Dover, 2001. - S. 117-120. - ISBN 0-486-41453-1 .
Andrzej Piotr Ruszczyński. optimización no lineal. — Princeton, NJ: Princeton University Press , 2006. — Pág. xii+454. - ISBN 978-0691119151 .
Christos H. Papadimitriou, Kenneth Steiglitz. Optimización Combinatoria: Algoritmos y Complejidad. - Dover, 1998. - ISBN 0-486-40258-4 .
Krzysztof C. Kiwiel, Torbjörn Larsson, P. O. Lindberg. Relajación lagrangiana a través de métodos de subgradiente ballstep // Matemáticas de investigación operativa. - 2007. - agosto ( vol. 32 , número 3 ). — S. 669–686 . - doi : 10.1287/moro.1070.0261 .