1
$\begingroup$

This is an example given in Algorithms for Convex Optimization by Vishnoi:

enter image description here

I'm trying to verify that what he gives is indeed the dual program, but for some reason I keep getting something different.


Here is my approach:

The Lagrangian is

$$ L(x, \lambda) = \sqrt{x} + \left(\frac{1}{x} - 1\right)\lambda. $$

The dual program is

$$ \sup_{\lambda \ge 0} \inf_{x \in \mathbb{R}} \left[ \sqrt{x} + \left(\frac{1}{x} - 1\right)\lambda \right]. $$

This tells me that it must be true that

$$ \inf_{x \in \mathbb{R}} \left[ \sqrt{x} + \left(\frac{1}{x} - 1\right)\lambda \right] =\frac{3}{2} \lambda - \frac{1}{2} \lambda^3 $$

for the textbook example to be correct. But for some reason this isn't what I'm getting. Taking the derivative of the left side, I get:

$$ \frac{d}{dx} \left[ \sqrt{x} + \left(\frac{1}{x} - 1\right)\lambda \right] = \frac{1}{2} x^{-1/2} - \lambda x^{-2}. $$

Setting this equal to $0$ yields the single critical point $x = (2 \lambda)^{2/3}$. Plugging this in yields:

$$ (2 \lambda)^{1/3} + 2^{-2/3} \lambda^{1/3} - \lambda, $$

which is completely different from what the textbook says.


Please let me know what I'm doing wrong. Thank you so much!

$\endgroup$
1
  • $\begingroup$ Actually, I think the textbook is just wrong here... $\endgroup$
    – nkyraf33
    May 14, 2021 at 19:36

1 Answer 1

1
$\begingroup$

You proceeded in the right direction. It remains to observe that your dual program is equivalent to the program in the book.

Proceeding from where you left. One can show that the critical point at $x=\left(2\lambda\right)^{1/3}$ is a global minimizer. This gives that \begin{align*} \inf_{x>0} \sqrt{x} + \lambda\left(\frac{1}x-1\right) % &= \left(2\lambda\right)^{1/3} + \frac{\lambda^{1/3}}{2^{2/3}}-\lambda\\ &= \frac32 \left(2\lambda\right)^{1/3}-\lambda. \end{align*} The resulting dual program is \begin{align*} \sup & ~~\frac32 \left(2\lambda\right)^{1/3}-\lambda\\ \text{s.t.}& ~~~ \lambda\geq 0. \end{align*} By changing the variable in the above program to $y=(2\lambda)^{1/3}$ we get the dual program stated in the book \begin{align*} \sup & ~~\frac32 y -\frac12 y^3\\ \text{s.t.}& ~~~ y\geq 0. \end{align*}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .