Dualidad (optimización)

En la teoría de la optimización matemática, la dualidad o el principio de dualidad es el principio según el cual los problemas de optimización pueden verse desde cualquiera de dos perspectivas, el problema primario b> o el problema dual. Si el primal es un problema de minimización, entonces el dual es un problema de maximización (y viceversa). Cualquier solución factible al problema primario (de minimización) es al menos tan grande como cualquier solución factible al problema dual (de maximización). Por lo tanto, la solución del primal es un límite superior de la solución del dual, y la solución del dual es un límite inferior de la solución del primal. Este hecho se llama dualidad débil.

En general, los valores óptimos de los problemas primario y dual no tienen por qué 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. Este hecho se llama dualidad fuerte.

Problema doble

Normalmente el término "problema dual" se refiere al problema dual lagrangiano pero se utilizan otros problemas duales, por ejemplo, el problema dual de Wolfe y el problema dual de Fenchel. El problema dual lagrangiano se obtiene formando el lagrangiano de un problema de minimización utilizando 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 restricciones).

En general dado dos pares duales de espacios separados localmente convexos ${\displaystyle \left(X,X^{*}\right)}$ y ${\displaystyle \left(Y,Y^{*}\right)}$ y la función ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty}$, podemos definir el problema primario como encontrar ${\displaystyle {\hat {x}}$ tales que ${\displaystyle f({\hat {x})=\inf _{x\in X}f(x).\,}$En otras palabras, si ${\displaystyle {\hat {x}}$ existe, ${\displaystyle f({\hat {x})}$ es el mínimo de la función ${\displaystyle f}$ y se alcanza el infimum (más alto límite) de la función.

Si hay condiciones de restricción, éstas se pueden construir en la función ${\displaystyle f}$ por dejar ${\displaystyle {\f}=f+I_{\mathrm} {constantes}}$ Donde ${\displaystyle I_{\mathrm {constraints}$ es una función adecuada en ${\displaystyle X}$ que tiene un mínimo 0 sobre las limitaciones, y para lo cual se puede probar que ${\displaystyle \inf _{x\in X}{\tilde {f}(x)=\inf _{x\\mathrm {constrained}f(x)}$. Esta última condición es trivial, pero no siempre convenientemente, satisfecho por la función característica (es decir,. ${\displaystyle I_{\mathrm {constraints}(x)=0}$ para ${\displaystyle x}$ satisfacción de las limitaciones y ${\displaystyle I_{\mathrm {constraints}(x)=\infty }$ de otro modo). Luego extiende ${\displaystyle {\f}}$ a una función de perturbación ${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty}$ tales que ${\displaystyle F(x,0)={\tilde {f}(x)}$.

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

${\displaystyle \sup _{y^{*}\in Y^{*}-F^{*}(0,y^{*})\leq \inf _{x\in X}F(x,0),\,}$

Donde ${\displaystyle F^{*}$ es el convex conjugado tanto en variables como ${\displaystyle \sup}$ denota el supremum (la parte superior).

Brecha de dualidad

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 primario óptimo, entonces la brecha de dualidad es igual a ${\displaystyle p^{*}-d^{*}$. Este valor es siempre mayor o igual a 0 (para problemas de minimización). La brecha de dualidad es cero si y sólo si la dualidad fuerte sostiene. De lo contrario la brecha es estrictamente positiva y débil dualidad sostiene.

En la optimización computacional, otra "brecha de dualidad" a menudo se informa, 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 principal. Esta alternativa de "brecha de dualidad" 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, bajo condiciones de regularidad, igual al valor de la relajación convexa del problema primal: La relajación convexa es el problema que surge reemplazando un conjunto factible no convexo por su convexo cerrado casco y con reemplazar una función no convexa con su cierre convexo, es decir, la función que tiene el epígrafe que es el casco convexo cerrado de la función objetivo primaria original.

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 de 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, existe 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 aquel 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 equivale 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 aquel 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 de Programación lineal: Dualidad.

Caso no lineal

En programación no lineal, las restricciones no son necesariamente lineales. No obstante, se aplican muchos de los mismos principios.

Para garantizar que el máximo global de un problema no lineal pueda identificarse fácilmente, la formulación del problema a menudo requiere que las funciones sean convexas y tengan conjuntos compactos de niveles inferiores. Ésta es la importancia 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 restricciones) 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.

Dualidad de Lagrange

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

${\displaystyle {\begin{aligned}{minimize } {\0}(x)\\\{\text{subject to } {\i} {\i}(x)\leq 0,\ i\in \left\{1,\ldotsm\right\}\end{aligned}}}}}}}}}}}} {\$

El problema tiene limitaciones; Nos gustaría convertirlo en un programa sin restricciones. Teóricamente, es posible hacerlo minimizando la función J(x), definida como

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

donde I es una función escalonada infinita: I[u]=0 si u≤0, y I[u]=∞ en caso contrario. Pero J(x) es difícil de resolver porque no es continuo. Es posible "aproximar" I[u] por λu, donde λ es una constante positiva. Esto produce una función conocida como lagrangiana:

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

Tenga en cuenta que, por cada x,

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

Prueba:

• Si x satisface todas las restricciones f_i()x)≤0, luego L(x,λ) se maximiza cuando se toma λ=0, y su valor es entonces f(x);
• Si x viola alguna restricción, f_i()x♪ ♪♪ i, entonces L(x,λ)→ cuando λ_i→.

Por lo tanto, el problema original es equivalente a:

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

Al invertir el orden de mínimo y máximo, obtenemos:

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

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

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

El Programa dual lagrangia es el programa de maximizar g:

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

La solución óptima del programa dual es un límite inferior para la solución óptima del programa original (primal); Este es el principio de dualidad débil. Si el problema primario es convexo y acotado desde abajo, 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 solución óptima del programa primario; Este es el principio de dualidad fuerte. En este caso, podemos resolver el programa primal encontrando una solución óptima λ* para el programa dual y luego resolviendo:

${\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 g(λ). En general, esto puede resultar difícil, ya que necesitamos resolver un problema de minimización diferente para cada λ. Pero para algunas clases de funciones, es posible obtener una fórmula explícita para g(). Resolver los programas primario y dual juntos suele ser más fácil que resolver solo uno de ellos. Algunos ejemplos 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 de la dualidad.

Otra condición en la que min-max y max-min son iguales es cuando el lagrangiano tiene un punto silla: (x∗, λ∗) es un punto silla de la función de Lagrange L si y solo si x∗ es un solución óptima al primal, λ∗ es una solución óptima al dual, y los valores óptimos en los problemas indicados son iguales entre sí.

El fuerte principio de Lagrange

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

${\fnMicrosoft Sans Serif} {\fnMimize } {\0} {\fnMicrosoft Sans Serif} {\f} {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif} {\f}\fnMicrosoft Sans Serif} {\fnMicrosoft}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\fnMicrox}\f}\f}\f}\fnMicros}\fnMicrosoft\fnMicrosoft,\f}\f\fnMicrosoft,\fnMicrosoft,\fnMicrosoft\fnMicrosoft,\fnMicrosoft,\f\f}\fnMicrosoft,\fnMicrosoft,\fnMicrosoft,\fnMicrosoft,\fnMicrosoft,\fnMicro$

con el dominio ${\displaystyle {\mathcal {}\subset \mathbb {R} {\fn}$ tener interior no vacío, el Función lagrangia ${\displaystyle {\Mathcal}:\mathbb {R} ^{n}\times \mathbb {R}\times \mathbb {R} ^{p}\to \mathbb {R}$ se define como

$[\displaystyle {\mathcal {L}(x,\lambda\nu)=f_{0}(x)+\sum ##{i=1} {m}\lambda ¿Por qué? ¿Qué?$

Los vectores ${\displaystyle \lambda }$ y ${\displaystyle \nu }$ son llamados Variables duales o Lagrange multiplier vectores asociado al problema. El 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 {\mthcal {}{\mthcal {}}(x,\lambda\nu)=\inf _{x\in {\in}\mthcal {}\left\{0}(x)+\sum ##{i=1} {m}\lambda ¿Por qué? ¿Por qué? - Sí.$

La función dual g es cóncavo, incluso cuando el problema inicial no es convexo, porque es un infimum de funciones de afin de punta. La función dual produce límites inferiores en 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 una calificación restrictiva como la condición de Slater sostiene y el problema original es convexo, entonces tenemos una fuerte dualidad, es decir. ${\displaystyle d^{*}=\max _{\lambda \geq 0,\nu }g(\lambda\nu)=\inf ¿Qué?$.

Problemas convexos

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

${\displaystyle {\begin{aligned} {x}{\operatorname {minimize}}}} {\\\\\fnMicrosoft Sans Serif} {\fnMinisterio} {\fnMinisterio} {\fnMinisterio}} {\fnMincipio}}}} {\fnMinisterio}}}}}}}}}}}}}}\\\\\\\\\\\\\\\\\fnMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinción\fnMinMinMinMinMinMinK\fnMinMinMinMinMinMinMinMinMinMinK\f}\f}\]\]\]\]\]\]\fnMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMincip]\fnMin$

el problema dual lagrangiano es

${\displaystyle {\begin{aligned} {\underset {u}{\operatorname {maximize}} {\inf_{x}\left(f(x)+\sum _{j=1}{m}u_{j}(x)\right)\f}\gnunció {subject\;to} {}} {\d}}} {\d}}}\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\cH00\c\c\cH00\c\cH00\c\cH00\c\cH00\c\c\cH00\c\cH00\c\c\c\cH$

donde la función objetiva es la función dual Lagrange. Siempre que las funciones ${\displaystyle f}$ y ${\displaystyle g_{1},\ldotsg_{m}$ son continuamente diferenciables, el infimum ocurre donde el gradiente es igual a cero. El problema

${\displaystyle {\begin{aligned} {\underset {x,u}{\operatorname {maximize}}} {duc(x)+\sum _{j=1} {m}u_{j}g_{j}(x)\fnuncio {subjeto\;to} > } > g_{j}(x)=0\\\ versedus tardes_{i}\gq 0,\quad i=1,\ldotsm\end{aligned}}}$

se llama el doble problema Wolfe. Este problema puede ser difícil de tratar computacionalmente, ya que la función objetiva no se concave en las variables conjuntas ${\displaystyle (u,x)}$. Además, la limitación de la igualdad ${\displaystyle \nabla f(x)+\sum _{j=1} {m}u_{j}\,\nabla g_{j}(x)}$ no es lineal en general, por lo que el problema dual Wolfe es típicamente un problema de optimización no convexa. En cualquier caso, la dualidad débil sostiene.

Historia

Según George Dantzig, el teorema de 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 señaló que estaba utilizando información de su teoría del juego, y conjetura que el juego de matriz de dos personas cero suma equivale a programación lineal. Las pruebas ridículas fueron publicadas por primera vez en 1948 por Albert W. Tucker y su grupo. (El prólogo de Dantzig a Nering y Tucker, 1993)

Aplicaciones

En las máquinas de vectores de soporte (SVM), la formulación del problema primario de las SVM como el problema dual se puede utilizar para implementar el truco del Kernel, pero este último tiene una mayor complejidad temporal en los casos históricos.