6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – learning Nov 10 '17 at 8:06
  • 1
    $\begingroup$ 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? $\endgroup$ – psmears Nov 10 '17 at 15:09
7
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.