Minimizing $x^{\frac32}$ over the non-negative reals as a SOCP

Question

I am trying to solve the following optimization problem (Problem 9.2) which can be setup as an SOCP.

$$ \begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & & x^{\frac{3}{2}} \\ & \text{subject to} & & x \geq 0 \end{aligned} \end{equation*} $$

I can restate it as follows $$ \begin{equation*} \begin{aligned} & \underset{x,\, t}{\text{minimize}} & & t \\ & \text{subject to} & x^{\frac{3}{2}} \leq t \\ & & x \geq 0,\, t \geq 0 \end{aligned} \end{equation*} $$

I can further simplify it by multiplying the inequality constraint by $\sqrt{x}$, which is positive, and thus the inequality remains unchanged. Then we substitute, $u = \sqrt{x}$ on the right-hand side to get the following problem. Here the variables t and u must also be non-negative $$ \begin{equation*} \begin{aligned} & \underset{x, \, t, \, u}{\text{minimize}} & & t \\ & \text{subject to} & x^2 \leq tu \\ & & u^2 = x \\ & & x \geq 0,\, t \geq 0,\, \geq 0 \end{aligned} \end{equation*} $$

Now I can split the quadratic equality constraint into 2 inequality constraints $$ \begin{equation*} \begin{aligned} & \underset{x, \, t, \, u}{\text{minimize}} & & t \\ & \text{subject to} & x^2 \leq tu \\ & & u^2 \leq x \\ & & u^2 \geq x \\ & & x \geq 0,\, t \geq 0,\, u \geq 0 \end{aligned} \end{equation*} $$

I can see how the first two constraints can be setup as 2 separate rotated cone constraints to give a valid SOCP. However, I don't understand how the author got rid of the third inequality constraint?

Answer 1

You don't need the $u^2 \geq x$ condition, as it never would be optimal to violate this constraint (to make $t$ small, you want to make $u^2$ large, hence the second constraint will be active)

Answer 2

The way is to introduce an additional variable and use two second-order cones. From $x^{3/2}\leq t$ we get

$$ x^{3/2} = \frac{x^{2}}{x^{1/2}}, $$

and therefore

$$ t\geq x^{3/2} \Rightarrow t x^{1/2}\geq x^2. $$

Introducing $s\geq 0$ we obtain

$$ 2st\geq x^2,\\ 2s\leq x^{1/2}, $$

that leads to

$$ 2st\geq x^2,\\ 1/4 x \geq s^{2}. $$

The overall problem takes the form:

$$ \min t\\ (t,s,x)\in \mathit{Q_r^3},\\ (1/8,x,s)\in \mathit{Q_r^3},\\ s,t,x\geq 0. $$

See http://docs.mosek.com/modeling-cookbook/cqo.html#simple-polynomial-sets for more details.