0
$\begingroup$

Can someone please explain how to convert the following into a second order cone programming formulation:

$\{(x,y,z,w,u): x,y,z,w \geq 0, (xyzw)^{\frac{1}{2}} \geq ||u||_2^2\}$

$\{(x,y,z,w,u): x,y,z,w \geq 0, (\prod_{k=1}^p x_k)^{\frac{1}{p}} \geq ||u||_2^2\}$ when $p = 2^n$ and $p \neq 2^n$

$\endgroup$
2
$\begingroup$

Assuming implicitly variables on the left-hand sides are nonnegative then $xy\geq u^2$ is a rotated (and rescaled) second order cone. Then

$$xy\geq s^2,\ zw\geq t^2,\ st\geq u^2$$

answers your first question, and so on. If the number of variables is not a power of 2 then take the next bigger power of 2 and fill some positions with the variable appearing on the right-hand side.

The older edition of the MOSEK Modeling Cookbook:

https://docs.mosek.com/MOSEKModelingCookbook-v2.pdf

has such things discussed in more detail Section 3.2.7, 3.2.11 and around.

I say older because the more recent MOSEK recommendation is to use the power cone or the exponential cone for geometric-mean modeling instead of rewriting with lots of second-order cones:

https://docs.mosek.com/modeling-cookbook/powo.html

$\endgroup$
  • $\begingroup$ Yes, I noticed V3 of the cookbook removed what I thought was still useful material from v2.3, which is why I kept v2.3 in addition to now using v3.1 $\endgroup$ – Mark L. Stone Dec 10 '19 at 15:13
  • $\begingroup$ Thanks for the link - I'm new to optimization so appreciate the extra resources. Just wondering, what's the benefit of adding all these extra "cone relationships", doesn't it make the problem more complicated to solve with all of these extra variables? $\endgroup$ – bilbo Dec 10 '19 at 20:40
  • $\begingroup$ @bilbo If you have a solver "only" capable of second-order cone and you need to express those sets then you have no choice - this is the only representation. Also, don't get tricked into thinking that complexity of a problem is just a simple function of the number of variables, it depends a lot more on the structure and sparsity. So adding a few variables in sparse constraints is reasonably cheap. $\endgroup$ – Michal Adamaszek Dec 11 '19 at 7:27

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.