Brecha de dualidad

En los problemas de optimización en matemáticas aplicadas , la brecha de dualidad es la diferencia entre las soluciones primal y dual . Si es el valor dual óptimo y es el valor primal óptimo, entonces la brecha de dualidad es igual a . 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 . ^{[ 1 ]}${\displaystyle d^{*}}$${\displaystyle p^{*}}$${\displaystyle p^{*}-d^{*}}$

En general, dados dos pares duales separados de espacios localmente convexos y , entonces, dada la función , podemos definir el problema primal mediante ${\displaystyle \left(X,X^{*}\right)}$${\displaystyle \left(Y,Y^{*}\right)}$${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \}}$

${\displaystyle \inf _{x\in X}f(x).\,}$

Si existen condiciones de restricción, estas pueden incorporarse a la función mediante donde es la función indicadora . Entonces, sea una función de perturbación tal que . La brecha de dualidad es la diferencia dada por ${\displaystyle f}$${\displaystyle f=f+I_{\text{restricciones}}}$${\displaystyle I}$${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \}}$${\displaystyle F(x,0)=f(x)}$

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

donde es el conjugado convexo en ambas variables. ^{[ 2 ] [ 3 ] [ 4 ]}${\displaystyle F^{*}}$

En 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 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 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 que tiene el epígrafo que es la envolvente convexa cerrada de la función objetivo primal original. ^{[ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ]}