2
$\begingroup$

Does Slater condition hold trivially (because there are no inequality constraints) for the problem:

$$\min_{x,y} \:\: cx+dy$$

s.t.

$$e^x + e^y = 1.$$

Can I conclude there is a zero duality gap here?

  • 1
    This site supports TeX markup, just enclose your formulas in dollar or double-dollar signs.2010-10-11
  • 0
    Okay. I am pretty sure this problem has zero duality gap. What some other condition can I use?2010-10-11

4 Answers 4

2

A Naga says, you can rewrite the equality constraint $h(x)=0$ as a pair of inequality constraints $$h(x) \leq 0$$ $$-h(x) \leq 0$$

The Slater condition would require $$h(x)<0$$ $$-h(x)<0$$ which is an impossibility. So the Slater condition cannot be true of a problem with equality constraints. Other regularity conditions may be usable though.

  • 0
    Your assertion regarding Slater's condition is false. It handles (linear) equality constraints just fine.2011-04-27
0

You can rewrite the equality constraint as $\exp{x} + \exp{y} \leq 1$ and $-\exp{x} -\exp{y} \leq -1$. If slater conditions hold for this new formulation, (since the problem is convex), strong duality (gap zero) would follow.

  • 0
    Slater theorem works only one way, and there are many "constraint qualifications" beyond convexity of the constraints that can establish strong duality (Boyd and Vandenberghe). This problem doesn't obey slaters as pointed out by Jyotirmoy.2010-10-11
0

I don't think the feasible space of the problem is a convex set. Why are you pretty sure that there is no dual gap?

I don't know what's the dual problem of this one, but we know the solution is $(x^*,y^*)=(\infty,0)$, that is unbounded.

0

You need to explain what dual you are talking about. Your problem is not convex so in theory, the concept of duality gap doesn't apply. Moreover, Slater's condition is only for inequality contraints of the form $g(x) \geq 0$ where $g$ is a concave function. Slater's condition will be satisfied if there exists an $x$ such that $g(x) > 0$.