Dualidad (optimización)

La brecha de dualidad es la diferencia entre los valores de cualquier solución primal y cualquier solución dual. Si${\displaystyle d^{*}}$es el valor dual óptimo y${\displaystyle p^{*}}$es el valor primal óptimo, entonces la brecha de dualidad es igual a${\displaystyle p^{*}-d^{*}}$Este valor siempre es mayor o igual que 0 (para problemas de minimización). La brecha de dualidad es cero si y solo si se cumple la dualidad fuerte . De lo contrario, la brecha es estrictamente positiva y se cumple la dualidad débil . ^{[ 5 ]}

En la optimización computacional, se suele informar de 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 primal. Esta "brecha de dualidad" alternativa cuantifica la discrepancia entre el valor de una iteración factible pero subóptima actual para el problema primal y el valor del problema dual; el valor del problema dual es, bajo ciertas condiciones de regularidad, igual al valor de la relajación convexa del problema primal: La relajación convexa es el problema que surge al reemplazar un conjunto factible no convexo con su envolvente convexa cerrada y al reemplazar una función no convexa con su clausura convexa , es decir, la función cuyo epígrafe es la envolvente convexa cerrada de la función objetivo primal original. ^{[ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ] [ 16 ]}

En el caso lineal, en el problema primal, desde cada punto subóptimo que satisface todas las restricciones, existe una dirección o subespacio de direcciones a las que moverse que incrementa la función objetivo. Se dice que moverse en cualquiera de estas direcciones elimina la holgura entre la solución candidata y una o más restricciones. Un valor inviable de la solución candidata es aquel que excede una o más restricciones.

En el problema dual, el vector dual multiplica las restricciones que determinan las posiciones de las restricciones en el problema primal. Variar el vector dual en el problema dual equivale a revisar los límites superiores en el problema primal. Se busca el límite superior más bajo. Es decir, se minimiza el vector dual para eliminar la holgura entre las posiciones candidatas de las restricciones y el óptimo real. Un valor inviable del vector dual es aquel demasiado bajo. Si este valor sitúa las posiciones candidatas de una o más restricciones en una posición que excluye el óptimo real.

Esta intuición se formaliza mediante las ecuaciones de Programación lineal: Dualidad .

Motivación ^{[ 17 ]}

Supongamos que queremos resolver el siguiente problema de programación no lineal :

${\displaystyle {\begin{aligned}{\text{minimizar }}&f_{0}(x)\\{\text{sujeto a }}&f_{i}(x)\leq 0,\ i\in \left\{1,\ldots ,m\right\}\\\end{aligned}}}$

El problema tiene restricciones; nos gustaría convertirlo en un programa sin restricciones. Teóricamente, es posible hacerlo minimizando la función.${\displaystyle J(x)}$, definido como

${\displaystyle J(x)=f_{0}(x)+\sum _{i}I[f_{i}(x)]}$

dónde${\displaystyle I}$es una función escalonada infinita :${\displaystyle I[u]=0}$si${\displaystyle u\leq 0}$, y${\displaystyle I[u]=\infty }$de lo contrario. Pero${\displaystyle J(x)}$es difícil de resolver ya que no es continuo. Es posible "aproximar"${\displaystyle I[u]}$por${\displaystyle \lambda u}$, dónde${\displaystyle \lambda }$es una constante positiva. Esto da como resultado una función conocida como el lagrangiano:

${\displaystyle L(x,\lambda )=f_{0}(x)+\sum _{i}\lambda _{i}f_{i}(x)}$

Tenga en cuenta que, por cada${\displaystyle x}$,

${\displaystyle \max _{\lambda \geq 0}L(x,\lambda )=J(x)}$.

Prueba :

• Si${\displaystyle x}$Satisface todas las restricciones${\displaystyle f_{i}(x)\leq 0}$, entonces${\displaystyle L(x,\lambda )}$se maximiza al tomar${\displaystyle \lambda =0}$y su valor es entonces${\displaystyle f(x)}$;
• Si${\displaystyle x}$viola alguna restricción,${\displaystyle f_{i}(x)>0}$para algunos${\displaystyle i}$, entonces${\displaystyle L(x,\lambda )\to \infty }$cuando${\displaystyle \lambda _ {i}\to \infty }$.

Por lo tanto, el problema original es equivalente a:

${\displaystyle \min _{x}\max _{\lambda \geq 0}L(x,\lambda )}$.

Al invertir el orden de min y max, obtenemos:

${\displaystyle \max _{\lambda \geq 0}\min _{x}L(x,\lambda )}$.

La doble función es el problema interno de la fórmula anterior:

${\displaystyle g(\lambda ):=\min _{x}L(x,\lambda )}$.

El programa dual lagrangiano es el programa de maximizar g:

${\displaystyle \max _{\lambda \geq 0}g(\lambda )}$.

La solución óptima del programa dual es una cota inferior para la solución óptima del programa original (primal); este es el principio de dualidad débil . Si el problema primal es convexo y acotado inferiormente, y existe un punto en el que todas las restricciones no lineales se satisfacen estrictamente ( condición de Slater ), entonces la solución óptima del programa dual es igual a la solución óptima del programa primal; este es el principio de dualidad fuerte . En este caso, podemos resolver el programa primal encontrando una solución óptima.${\displaystyle \lambda ^{*}}$al programa dual y luego resolver:

${\displaystyle \min _{x}L(x,\lambda ^{*})}$.

Tenga en cuenta que, para utilizar el principio de dualidad débil o fuerte, necesitamos una forma de calcular${\displaystyle g(\lambda )}$En general, esto puede ser difícil, ya que necesitamos resolver un problema de minimización diferente para cada${\displaystyle \lambda }$. Pero para algunas clases de funciones, es posible obtener una fórmula explícita para${\displaystyle g(\lambda )}$Resolver los programas primal y dual conjuntamente suele ser más fácil que resolver solo uno de ellos. Ejemplos de ello son la programación lineal y la programación cuadrática . El teorema de dualidad de Fenchel proporciona un enfoque mejor y más general para la dualidad . ^{[ 18 ] : Sub.3.3.1}

Otra condición en la que min-max y max-min son iguales es cuando el lagrangiano tiene un punto de silla :${\displaystyle (x^{*},\lambda ^{*})}$es un punto de silla de la función de Lagrange${\displaystyle L}$si y solo si${\displaystyle x^{*}}$es una solución óptima para el problema primordial,${\displaystyle \lambda ^{*}}$es una solución óptima para el dual, y los valores óptimos en los problemas indicados son iguales entre sí. ^{[ 18 ] : Prop.3.2.2}

Dado un problema de programación no lineal en forma estándar

${\displaystyle {\begin{aligned}{\text{minimize }}&f_{0}(x)\\{\text{subject to }}&f_{i}(x)\leq 0,\ i\in \left\{1,\ldots ,m\right\}\\&h_{i}(x)=0,\ i\in \left\{1,\ldots ,p\right\}\end{aligned}}}$

con el dominio${\displaystyle {\mathcal {D}}\subset \mathbb {R} ^{n}}$Al tener un interior no vacío, la función lagrangiana${\displaystyle {\mathcal {L}}:\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R} }$se define como

${\displaystyle {\mathcal {L}}(x,\lambda ,\nu )=f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x).}$

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

${\displaystyle g(\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}{\mathcal {L}}(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)\right\}.}$

La doble función${\displaystyle g}$es cóncava, incluso cuando el problema inicial no es convexo, porque es un ínfimo puntual de funciones afines. La función dual proporciona cotas inferiores para el valor óptimo.${\displaystyle p^{*}}$del problema inicial; para cualquier${\displaystyle \lambda \geq 0}$y cualquier${\displaystyle \nu }$tenemos${\displaystyle g(\lambda ,\nu )\leq p^{*}}$.

Si se cumple una condición de cualificación de restricciones como la condición de Slater y el problema original es convexo, entonces tenemos dualidad fuerte , es decir${\displaystyle d^{*}=\max _{\lambda \geq 0,\nu }g(\lambda ,\nu )=\inf f_{0}=p^{*}}$.

Para un problema de minimización convexa con restricciones de desigualdad,

${\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\ldots ,m\end{aligned}}}$

El problema dual lagrangiano es

${\displaystyle {\begin{aligned}&{\underset {u}{\operatorname {maximize} }}&&\inf _{x}\left(f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\right)\\&\operatorname {subject\;to} &&u_{i}\geq 0,\quad i=1,\ldots ,m\end{aligned}}}$

donde la función objetivo es la función dual de Lagrange. Siempre que las funciones${\displaystyle f}$y${\displaystyle g_{1},\ldots ,g_{m}}$son continuamente diferenciables, el ínfimo se produce donde el gradiente es igual a cero. El problema

${\displaystyle {\begin{aligned}&{\underset {x,u}{\operatorname {maximize} }}&&f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\\&\operatorname {subject\;to} &&\nabla f(x)+\sum _{j=1}^{m}u_{j}\,\nabla g_{j}(x)=0\\&&&u_{i}\geq 0,\quad i=1,\ldots ,m\end{aligned}}}$

Se denomina problema dual de Wolfe . Este problema puede ser difícil de abordar computacionalmente, porque la función objetivo no es cóncava en las variables conjuntas.${\displaystyle (u,x)}$Además, la restricción de igualdad${\displaystyle \nabla f(x)+\sum _{j=1}^{m}u_{j}\,\nabla g_{j}(x)}$En general, es no lineal, por lo que el problema dual de Wolfe es típicamente un problema de optimización no convexo. En cualquier caso, se cumple la dualidad débil . ^{[ 19 ]}

• 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 convexo y optimización . 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. pp.  xiv+490. doi : 10.1007/978-3-540-35447-5 . ISBN 3-540-35445-XMR 2265882 .​ 
• Cook, William J .; Cunningham, William H.; Pulleyblank, William R .; Schrijver, Alexander (12 de noviembre de 1997). Optimización combinatoria (1.ª  ed.). John Wiley & Sons. ISBN 0-471-55894-X.
• Dantzig, George B. (1963). Programación lineal y extensiones . Princeton, NJ: Princeton University Press.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Algoritmos de minimización y análisis convexo, Volumen  I: Fundamentos . Grundlehren der Mathematischen Wissenschaften [Principios fundamentales de las ciencias matemáticas]. vol.  305. Berlín: Springer-Verlag. págs.  xviii+417. ISBN 3-540-56850-6. MR 1261420 . 
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). "14 Dualidad para los profesionales". Algoritmos de minimización y análisis convexo, Volumen  II: Teoría avanzada y métodos de paquetes . Grundlehren der Mathematischen Wissenschaften [Principios fundamentales de las ciencias matemáticas]. vol.  306. Berlín: Springer-Verlag. págs.  xviii+346. ISBN 3-540-56852-2MR 1295240 .​ 
• Lasdon, Leon  S. (2002) [Reimpresión de la edición de 1970 de Macmillan]. Teoría de la optimización para sistemas grandes . Mineola, Nueva York: Dover Publications, Inc. pp.  xiii+523. ISBN 978-0-486-41999-2. MR 1888251 . 
• Lawler, Eugene (2001). "4.5. Implicaciones combinatorias del teorema de flujo máximo y corte mínimo, 4.6. Interpretación de programación lineal del teorema de flujo máximo y corte mínimo". Optimización combinatoria: redes y matroides . Dover. pp. 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 . Apuntes de conferencias en informática (LNCS). vol.  2241. Berlín: Springer-Verlag. págs. 112-156 . doi : 10.1007/3-540-45586-8_4 . ISBN  3-540-42877-1. MR 1900016 . S2CID 9048698 .  
• Minoux, Michel (1986). Programación matemática: Teoría y algoritmos . Egon Balas (prólogo); Steven Vajda (trad.) del francés. Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd. (1983 París: Dunod). pp.  xxviii+489. ISBN 0-471-90170-9. SEÑOR 0868279 . (2008 Segunda ed., en francés: Programmation mathématique : Théorie et algoritmos , Éditions Tec & Doc, París, 2008. xxx+711 pp.)).  
• Nering, Evar D.; Tucker, Albert W. (1993). Programación lineal y problemas relacionados . Boston, MA: Academic Press. 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, NJ: Princeton University Press . págs.  xii+454. ISBN 978-0-691-11915-1MR 2199043 .​ 

• Everett, Hugh III (1963). «Método generalizado de multiplicadores de Lagrange para resolver problemas de asignación óptima de recursos» . Operations Research . 11 (3): 399– 417. doi : 10.1287/opre.11.3.399 . JSTOR 168028. MR 0152360. Archivado del original el 24 de julio de 2011.  
• Kiwiel, Krzysztof  C.; Larsson, Torbjörn; Lindberg, P.  O. (agosto de 2007). "Relajación lagrangiana mediante métodos de subgradiente de paso de bola" . Mathematics of Operations Research . 32 (3): 669– 686. doi : 10.1287/moor.1070.0261 . MR 2348241. Archivado del original el 26 de julio de 2011. Recuperado el 12 de mayo de 2011 . 
• Dualidad en la programación lineal Gary D. Knott