I have to solve the following optimization problem: $$ \begin{align*} \min_{x,y} &\{-x-y\} \\ \text{such that} \\ y &\ge 3 \\ y &\le 30 \\ x &\ge 0 \\ xy &\le 1 \\ \end{align*} $$ I want to use a second order cone programming (SOCP) solver because the rest of my problem (not shown here) can be formulated as a second order cone program. However, my problem is the $xy\le 1$ hyperbolic constraint that has the inequality "the wrong way" to be written as a second order cone. It would be great if you could show me for this toy problem how one might deal with the $xy\le 1$ constraint. Thanks a lot!

  • $\begingroup$ $0\le x\le\frac{1}{y}$ and $y\ge 3$ imply $0\le x\le\frac{1}{3}$. So we clearly minimise by taking $y=30,x=\frac{1}{30}$. $\endgroup$ – almagest Apr 26 '16 at 9:06
  • $\begingroup$ Yeah, but my question is how to reformulate it for a computer convex solver to solve, not by hand. This is an example problem of a much more complicated problem that I'm dealing with. $\endgroup$ – space_voyager Apr 26 '16 at 9:09
  • $\begingroup$ I would say that it is not possible to formulate your problem as a convex optimization problem. $\endgroup$ – gerw Apr 26 '16 at 10:35
  • $\begingroup$ @gerw is correct. It's not convex. $\endgroup$ – Michael Grant Apr 27 '16 at 16:00
  • $\begingroup$ @MichaelGrant I've not gone over the theory of convex optimization. Is it generally true that if a constraint is non-convex, then it is impossible to make it convex? Perhaps there are techniques to convexify this constraint? $\endgroup$ – space_voyager Apr 28 '16 at 21:33

The constraint $xy\le1$ is non-convex, so the problem cannot be solved as stated using SOCP techniques.


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.