Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
This site supports TeX markup, just enclose your formulas in dollar or double-dollar signs. –  Jyotirmoy Bhattacharya Oct 11 '10 at 4:29
    
Okay. I am pretty sure this problem has zero duality gap. What some other condition can I use? –  normvector Oct 11 '10 at 15:58

4 Answers 4

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.

share|improve this answer
    
Your assertion regarding Slater's condition is false. It handles (linear) equality constraints just fine. –  cardinal Apr 27 '11 at 11:42

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.

share|improve this answer

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$.

share|improve this answer

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.

share|improve this answer
    
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. –  Naga Oct 11 '10 at 4:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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