5
$\begingroup$

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!

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for your detailed response! It's pretty neat that this works sometimes. Are there conditions such that it's always true that the duality gap is tightened (or at least not made worse)? $\endgroup$ – user477739 May 11 '18 at 14:42
  • $\begingroup$ @user477739 Removing a constraint makes the supremum of the dual function less than or equal to what it was before, since $$\sup_{\mu\geq 0, \lambda \geq 0} d(\mu,\lambda) \geq \sup_{\mu\geq 0} d(\mu,0)$$ where setting $\lambda =0$ essentially removes the constraint associated with the multiplier $\lambda$. If the removed constraint was redundant, the optimal primal objective value does not change, so the duality gap either increases or stays the same after removal. Likewise, the duality gap cannot get worse when we add a redundant constraint, it can only either stay the same or get better. $\endgroup$ – Michael May 11 '18 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.