I am solving problem 5.22 b) from Boyd and Vanderberghe "Convex Optimization". The problem is that given the optimization problem $$\begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & & x \\ & \text{subject to} & & x^2 \leq 0\\ \end{aligned} \end{equation*}$$

I need to find the dual and the primal and dual optimal points. I found that the dual problem is

\begin{equation*} \begin{aligned} & \underset{x}{\text{maximize}} & & -\frac{1}{4\lambda} \\ & \text{subject to} & & \lambda>0 \end{aligned} \end{equation*}

And from this, I concluded hat the optimal point is $p^* = 0$ for $x^* = 0$. However, my conclusion for the dual was that we could not attain the dual optimal point. Thus, there is strong duality HOWEVER, the solutions say that the dual optimal is $d^* = 0$ but it is not achieved and so there is strong duality. I don't understand why the answer gives you an optimal dual $d^*$ and then says you can't achieve it. If you can't achieve it, then why to give it? Also, if we can't achieve it, how do we have strong duality? Maybe I did something wrong when computing the dual problem? Thanks for your help!

  • $\begingroup$ The dual is $\inf_{\lambda \ge 0} - {1 \over 4 \lambda} = 0$, but is not attained. $\endgroup$ – copper.hat Nov 29 '17 at 7:06
  • $\begingroup$ Why is it $\inf_{\lambda \geq 0} -\frac{1}{4\lambda}$? Wasn't it supposed to be that in the dual we maximize $g(x,\lambda)$ where $g(x,\lambda) = \inf_x L(x,\lambda)$ where $L(x,\lambda)$ is the Lagrangian (followin Boyd)? how did you get that we should maximize the infimum and not only $-\frac{1}{4\lambda}$? $\endgroup$ – user110320 Nov 29 '17 at 7:31
  • $\begingroup$ I think the difficulty here is that @user110320 doesn't understand the difference between $\min$ and $\inf$. $\endgroup$ – Brian Borchers Nov 29 '17 at 14:59
  • 1
    $\begingroup$ I suspect @BrianBorchers has a point. A $\min$ means a lower bound that is attained at some point, $\inf$ is the greatest lower bound which mightt not be achieved (example, $\inf_x {1 \over 1+x^2}$). Very loosely speaking one has a primal $\inf_x \sup_\lambda L(x, \lambda)$ and to get the dual, one swaps the $\inf,\sup$ to get $\sup_\lambda \inf_x L(x, \lambda)$. If these values are the same some authors refer to this as strong duality (it is easy to show that the dual is always $\le $ the primal). Strong duality does not imply the existence of an extremising point (saddle) as the above shows. $\endgroup$ – copper.hat Nov 29 '17 at 17:55
  • $\begingroup$ I see. This makes sense. I guess I got confused with the fact that the book uses the word minimize, so I thought we were looking for the $\min$, not necessarily the $\inf$. $\endgroup$ – user110320 Nov 30 '17 at 4:37

Your Answer

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

Browse other questions tagged or ask your own question.