Improving duality gap by adding redundant inequalities Suppose I have an optimization problem minimize $ f_0(x) $ subject to $ f_i(x) \leq 0, $ for $ i = 1,\ldots,m $. I'm not assuming any of these functions are convex.  I have heard various people casually mention that by adding a redundant inequality constraint $ \tilde{f}(x) \leq 0 $ (that is, $ f_i(x) \leq 0, $ for $ i = 1,\ldots,m $ implies that $ \tilde{f}(x) \leq 0 $) the duality gap between the primal and dual problem can be tightened.
Is this true?
I've been unable to find an answer in Boyd & Vandenberghe or one of Bertsekas's books, and I couldn't find anything online.  I tried to prove it, but after noodling around for a while with the max-min inequality, I've got nothing but trivialities.
If it's true, please provide a proof or a link to a proof.  If it's false, are there conditions under which it's true?
Thanks!
 A: Yes.  It does not always work, so using this technique is more of an art. 
Here is an example that shows a duality gap of $-\infty$ can be improved to a gap of 0 by adding a redundant constraint: 
Original problem:
Define $\mathcal{X} = \{x \in \mathbb{R} : x\geq 0\}$. Consider
\begin{align}
\mbox{Minimize:} \quad & 1-x^2\\
\mbox{Subject to:} \quad & x \leq 1/2 \\
& x \in \mathcal{X}
\end{align}
so that $f(x) = 1-x^2$ is not convex. The optimal solution is $x^*=1/2$, $f(x^*)=3/4$. 
The dual function is defined for $\mu \geq 0$ by 
$$ d(\mu) = \inf_{x \in \mathcal{X}} [1-x^2 + \mu (x-1/2)] = -\infty \quad \forall \mu \geq 0$$
So there is an infinite duality gap. 
Redundant constraint:
Consider the equivalent problem that adds the redundant constraint $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}
The dual function defined for $\mu\geq 0, v\geq 0$ is
\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 $v \in [0,1)$} \\
1-\mu/2 - v/4  & \mbox{ otherwise} 
\end{array}
\right.
\end{align}
and the maximum of $d(\mu,v)$ occurs when $v=1, \mu=0$: 
$$ d(0,1) = 3/4 = f(x^*)$$
and so the new problem has zero duality gap!  

FYI: A while ago a student of mine considered a similar idea for an information theory "index coding" problem: We represented the same non-convex problem in a different way to improve on a duality gap, which leads to improved coding schemes. In the link below, Problems P1 and P6 are equivalent but the representation P6 yields a smaller duality gap and leads to better "partial clique" codes:
http://ee.usc.edu/stochastic-nets/docs/duality-codes-it.pdf
