For a convex optimization problem, if primal and dual optimal variables exist, does strong duality hold?

Question

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?

Answer 1

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.

Answer 2

I found an example here, which I'll summarize below.

Consider the optimization problem \begin{align} \operatorname{minimize} & \quad e^{-x} \\ \text{subject to} & \quad \frac{x^2}{y} \leq 0. \end{align} The domain for the problem is $D = \{ (x,y) \mid y > 0 \}$. It can be shown that this problem is convex. Clearly, $x = 0, y = 1$ is a primal optimal solution.

The Lagrangian is $$ L(x,y,z) = e^{-x} + \frac{z x^2}{y}. $$ The dual function is \begin{align} G(z) &= \inf \, \left\{ e^{-x} + \frac{z x^2}{y} \mid y > 0 \right\}. \end{align} You can check that $G(z) = 0$ for all $z \geq 0$. Thus, any $z \geq 0$ is a dual optimal solution.

So, this is a problem for which primal and dual optimal variables exist, but strong duality fails to hold.