Is there a convex optimization problem such that a primal optimal solution exists, and a dual optimal solution exists, but the primal optimal value is not equal to the dual optimal value?
[Math] For a convex optimization problem, if primal and dual optimal variables exist, does strong duality hold
convex optimization
Best Answer
No. Here is a standard counter-example (perhaps also found elsewhere on this site?)
Define $\mathcal{X} = [0,1]$. Define the convex function $f:\mathcal{X}\rightarrow\mathbb{R}$ by
$$f(x) = \left\{ \begin{array}{ll} 1 &\mbox{ if $x =0$} \\ 0 & \mbox{ if $x \in (0,1]$} \end{array} \right.$$ Then consider the convex program: \begin{align} \mbox{Minimize:} & \quad f(x) \\ \mbox{Subject to:} & \quad x \leq 0 \\ & \quad x \in \mathcal{X} \end{align} The optimal solution to the primal is $x^*=0$ and $f(x^*)=1$. The dual function (defined for $\mu\geq 0$) is: $$ d(\mu) = \inf_{x \in \mathcal{X}} [f(x) + \mu x] =0 \quad \forall \mu \geq 0 $$ So the dual function is constant, in particular $\mu^*=0$ maximizes the dual function and $d(\mu^*)=0$. So $d(\mu^*)<f(x^*)$ and we have a duality gap of 1.