Derive the dual program of this nonconvex program

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

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!

• Actually, I think the textbook is just wrong here... May 14, 2021 at 19:36

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*}