# Lagrange function and strong duality in an optimization problem

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.

## 1 Answer

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

• 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? Commented Apr 8, 2022 at 10:10
• @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.
– f10w
Commented Apr 8, 2022 at 13:28