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!
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