Suppose, we have following convex optimization problem:
$$\
\min_x\psi(x) \ \ s.t. \ \phi(x) \leq 0
$$
We can write the primal problem as:
$$\
\min_x\max_{\lambda\geq 0} \psi(x) + \lambda\phi(x)
$$
and the dual problem as:
$$\
\max_{\lambda\geq 0}\min_x \psi(x) + \lambda\phi(x)
$$
Let's say $(\bar x, \bar \lambda)$ is the solution to primal problem and $(x^*, \lambda^*)$ solution to dual problem. Assuming $\psi$ and $\phi$ are not strictly convex, primal solution need not be the same as dual solution i.e. $x^* \neq \bar x$ and $\lambda^* \neq \bar\lambda$. However strong duality tell us that, $\mathcal L (\bar x, \bar \lambda) = \mathcal L(x^*, \lambda^*)$. Can you point me to some interesting example for the same or give an intuition? I understand the problem does not have unique saddle point and hence this issue. I still have conceptual doubts, will $(x^*, \lambda^*)$ not satisfy the K.K.T conditions for the original constrained optimization problem?
Edit: I am confused because often people talk about methods for getting primal solution from the dual solution. Paper Page 56 (Applying Minimax theorem line) tells that the approximate solution is in the convex hull of dual iterates. Well my question is why not take the last iterate of dual?
Best Answer
The KKT conditions of the primal and the dual problem are identical if the primal solution is attained. The primal problem is: $$\ \min_x\max_{\lambda\geq 0} \psi(x) + \lambda\phi(x) \qquad(P) $$ Its KKT conditions are $\phi(x) \leq 0$ (primal feasibility), $\lambda\geq 0$ (dual feasibility) $\psi'(x) + \lambda \phi'(x)=0$ (stationarity) and $\lambda \phi(x)=0$ (complementarity).
The dual problem is: $$\ \max_{\lambda\geq 0}\min_x \psi(x) + \lambda\phi(x) \qquad(D) $$ which is equivalent to: $$\ \max_{\lambda} \min_{y\geq 0, x} \psi(x) + \lambda\phi(x) + \lambda y \qquad(D) $$ The stationarity condition is $\phi(x) + y = 0$ (i.e., $\phi(x)\leq 0$). The primal feasibility conditions are $\lambda \geq 0$ (as otherwise the value of $\min_{y\geq 0}$ is $-\infty$) and $\min_x \psi(x) + \lambda \phi(x)>-\infty$. For the latter, if the minimum is attained (i.e., the primal problem can be solved), you have $\psi'(x) + \lambda \phi'(x)=0$. The complementarity condition is $\lambda y = 0$ (which implies $\lambda \phi(x)=0$ via the stationarity condition).