# 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. Commented Nov 10, 2017 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? Commented Nov 10, 2017 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. Commented Nov 10, 2017 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.