0
$\begingroup$

Suppose we have an (not necessarily convex) optimization problem : $$\begin{split}\min_x f_0(x)\\ f_1(x)\leq 0. \end{split}$$ Let $L(x,\lambda)=f_0(x)+\lambda(f_1(x))$. Then the above problem can be equivalently written as: $$\min_x \max_{\lambda\geq 0} L(x,\lambda).$$
The dual of the above problem can be written as: $$\max_{\lambda \geq 0} \min_{x} L(x,\lambda).$$ We say that strong duality holds at a point when $$\min_x \max_{\lambda\geq 0} L(x,\lambda)=\max_{\lambda \geq 0} \min_{x} L(x,\lambda).$$ By weak duality, the inequality $$\min_x \max_{\lambda\geq 0} L(x,\lambda)\geq\max_{\lambda \geq 0} \min_{x} L(x,\lambda)$$ always holds true. My doubt is: suppose there exists an $x^*$ that minimizes $L(x,\lambda)$ for a fixed $\lambda$, can i say that the following inequality holds true: $$\max_{\lambda \geq 0} \big(\min_{x} L(x,\lambda)\big)=\max_{\lambda \geq 0}L(x^*,\lambda) \geq \min_x \max_{\lambda\geq 0} L(x,\lambda).$$ If the above is true, then are we saying that if there is a primal variable that attains its minimum in the dual problem, then strong duality holds true? Somewhere this does not seem to add up.

$\endgroup$

1 Answer 1

0
$\begingroup$

No, because the last inequality, $\max_{\lambda \geq 0}L(x^*,\lambda) \geq \min_x \max_{\lambda\geq 0} L(x,\lambda)$, does not hold in general. Note that $x^*$ is a function of $\lambda$. It would have been clearer to write $x^*(\lambda)$ instead of just $x^*$.

$\endgroup$
2
  • $\begingroup$ I agree that x^* is a function of \lambda. So we have \max_{\lambda \geq 0}L(x^*(\lambda),\lambda). If we see x^*(\lambda) as an arbitrary first component, then won't the inequality hold true? $\endgroup$ Commented Apr 8, 2022 at 10:10
  • $\begingroup$ @Cherryblossoms Except that $x^*(\lambda)$ is not arbitrary, because it depends on $\lambda$, so the argument is not valid. You may want to introduce the notation $g(x) = \max_{\lambda\geq 0} L(x,\lambda)$, that could help clarify a bit if what I say is not clear enough. $\endgroup$
    – f10w
    Commented Apr 8, 2022 at 13:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .