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

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?

• Short answer: Yes. There must be certain conditions, like constraint qualifications, that hold. For example, see Slater's Condition. If not satisfied, Strong Duality won't hold, and there will be a duality gap. – learning Nov 10 '17 at 8:06
• The question in the body asks the opposite of what's in the title. That means it's confusing when people answer "Yes" or "No" - are they answering the question in the title, or the one in the body? Can you edit one or the other to make them consistent? – psmears Nov 10 '17 at 15:09

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.

• I see there is another nice example with continuous functions given below. – Michael Nov 10 '17 at 7:54

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.