# Second Order Cone Program

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?

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)

• There is no constraint such as $u^2 \geq t$ in the problem – Rohit Arora Dec 26 '15 at 13:53
• The larger I make $u$, the smaller I can make $t$ to keep the first constraint active. The second constraint restricts that movement of $u$ to the domain $\left[0,\sqrt{x}\right]$. The third constraint restricts that movement to the domain $\left[\sqrt{x},\infty\right)$. Dropping the second instead of third constraint gives me a greater reduction in t. So, why should I keep the second and drop the third constraint ? – Rohit Arora Dec 26 '15 at 14:52
• I meant $u^2 \geq x$. You keep the second constraint to ensure $u^2 = x$ at optimality. – Johan Löfberg Dec 27 '15 at 9:45

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},$$

$$2st\geq x^2,\\ 1/4 x \geq s^{2}.$$
$$\min t\\ (t,s,x)\in \mathit{Q_r^3},\\ (1/8,x,s)\in \mathit{Q_r^3},\\ s,t,x\geq 0.$$
• Thanks I saw that on Mosek's website. My problem has always been with the introduction of $2s \leq x^{1/2}$ constraint. I would always start with saying $2s = x^{1/2}$ and then splitting into 2 constraints, $2s \leq x^{1/2}$ and $2s \geq x^{1/2}$. Sadly, I always found that docs trivially removed the constriant, $2s \geq x^{1/2}$ without any justification, including the one cited above from Mosek. – Rohit Arora Dec 29 '15 at 15:48
• @Andrea I am working on a quadratic programming problem where after getting rid of the $x$ in the Lagrangian, I can't figure out how to find the dual problem. Can you please help? There is a 100 point bounty on the question: math.stackexchange.com/questions/2571031/… – ALannister Dec 23 '17 at 2:42