Carolyn Beck

2022-06-24

Suppose we have an (not necessarily convex) optimization problem :
$\begin{array}{r}\underset{x}{min}{f}_{0}\left(x\right)\\ {f}_{1}\left(x\right)\le 0.\end{array}$
Let $L\left(x,\lambda \right)={f}_{0}\left(x\right)+\lambda \left({f}_{1}\left(x\right)\right)$. Then the above problem can be equivalently written as:
$\underset{x}{min}\underset{\lambda \ge 0}{max}L\left(x,\lambda \right).$
The dual of the above problem can be written as:
$\underset{\lambda \ge 0}{max}\underset{x}{min}L\left(x,\lambda \right).$
We say that strong duality holds at a point when
$\underset{x}{min}\underset{\lambda \ge 0}{max}L\left(x,\lambda \right)=\underset{\lambda \ge 0}{max}\underset{x}{min}L\left(x,\lambda \right).$
By weak duality, the inequality
$\underset{x}{min}\underset{\lambda \ge 0}{max}L\left(x,\lambda \right)\ge \underset{\lambda \ge 0}{max}\underset{x}{min}L\left(x,\lambda \right)$
always holds true. My doubt is: suppose there exists an ${x}^{\ast }$ that minimizes $L\left(x,\lambda \right)$ for a fixed $\lambda$, can i say that the following inequality holds true:
$\underset{\lambda \ge 0}{max}\left(\underset{x}{min}L\left(x,\lambda \right)\right)=\underset{\lambda \ge 0}{max}L\left({x}^{\ast },\lambda \right)\ge \underset{x}{min}\underset{\lambda \ge 0}{max}L\left(x,\lambda \right).$
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.

Harold Cantrell

No, because the last inequality, $\underset{\lambda \ge 0}{max}L\left({x}^{\ast },\lambda \right)\ge \underset{x}{min}\underset{\lambda \ge 0}{max}L\left(x,\lambda \right)$, does not hold in general. Note that ${x}^{\ast }$ is a function of λ. It would have been clearer to write x∗(λ) instead of just ${x}^{\ast }$.