0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ There is no constraint such as $u^2 \geq t$ in the problem $\endgroup$ – Rohit Arora Dec 26 '15 at 13:53
  • $\begingroup$ 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 ? $\endgroup$ – Rohit Arora Dec 26 '15 at 14:52
  • $\begingroup$ I meant $u^2 \geq x$. You keep the second constraint to ensure $u^2 = x$ at optimality. $\endgroup$ – Johan Löfberg Dec 27 '15 at 9:45
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Rohit Arora Dec 29 '15 at 15:48
  • $\begingroup$ @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/… $\endgroup$ – ALannister Dec 23 '17 at 2:42

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.