Sí. No siempre funciona, por lo que el uso de esta técnica es más un arte.
Aquí está un ejemplo que muestra una dualidad brecha de $-\infty$ puede ser mejorado para un hueco de 0 mediante la adición de una restricción redundante:
Problema Original:
Definir $\mathcal{X} = \{x \in \mathbb{R} : x\geq 0\}$. Considere la posibilidad de
\begin{align}
\mbox{Minimize:} \quad & 1-x^2\\
\mbox{Subject to:} \quad & x \leq 1/2 \\
& x \in \mathcal{X}
\end{align}
de modo que $f(x) = 1-x^2$ no es convexa. La solución óptima es $x^*=1/2$, $f(x^*)=3/4$.
La doble función está definida para $\mu \geq 0$ por
$$ d(\mu) = \inf_{x \in \mathcal{X}} [1-x^2 + \mu (x-1/2)] = -\infty \quad \forall \mu \geq 0$$
Así que hay un infinito dualidad de la brecha.
Restricciones redundantes:
Considerar el equivalente problema que agrega las restricciones redundantes $x^2 \leq 1/4$:
\begin{align}
\mbox{Minimize:} \quad & 1-x^2\\
\mbox{Subject to:} \quad & x \leq 1/2 \\
& x^2 \leq 1/4\\
& x \in \mathcal{X}
\end{align}
La doble función definida por $\mu\geq 0, v\geq 0$ es
\begin{align}
d(\mu, v) &= \inf_{x\in \mathcal{X}}[1-x^2 + \mu(x-1/2) + v(x^2-1/4)]\\
&= \left\{ \begin{array}{ll}
-\infty &\mbox{ if %#%#%} \\
1-\mu/2 - v/4 & \mbox{ otherwise}
\end{array}
\right.
\end{align}
y el máximo de $v \in [0,1)$ se produce cuando $d(\mu,v)$:
$v=1, \mu=0$$
y así, el nuevo problema que tiene cero de la dualidad de la brecha!
FYI: hace UN tiempo una de mis estudiantes considera una idea similar para una teoría de la información "índice de codificación" problema: representamos a la misma no convexa problema de una manera diferente para mejorar en una dualidad de la brecha, lo que conduce a la mejora de los esquemas de codificación. En el enlace a continuación, los Problemas P1 y P6 son equivalentes, pero la representación P6 produce un menor dualidad brecha y conduce a una mejor "parcial " camarilla" códigos:
http://ee.usc.edu/stochastic-nets/docs/duality-codes-it.pdf
