I have this optimization problem:

$$x_{1} \cdot x_{2} \geq (x_3)^2$$ where \(x_1, x_2 \geq 0\)

I know this is a rotated second-order cone, which can be transformed into a cone using this formulation: $$\lVert [x_{1} - x_{2},\ 2\cdot x_3] \rVert \leq x_{1} + x_{2}$$

However, as I expand my optimization model, I added a linear term to my constraint:

$$x_{1} \cdot x_{2} \geq (x_3)^2 - x_3$$

I have tried to express this as a second-order cone but I am pretty sure it is not possible. Could you help me identify which type of constraint this is, and which type of optimization program I could use to solve it? (the rest of the constraints in my model and the objective function are linear)

asked 16 Oct '17, 14:15

Luis%20Badesa's gravatar image

Luis Badesa
accept rate: 0%

edited 16 Oct '17, 16:54

With the linear term, it is not a Second Order Cone Program, because it is not convex. So you need a solver which can handle non-convex constraints.

Counter-example which shows this is non-convex:
Point A = (0,0,0) and point B = (1,1,-0.5) both satisfy the constraints. The convex combination, C = 0.5*(A + B), does not satisfy the constraints.


answered 22 Oct '17, 15:26

Mark%20L%20Stone's gravatar image

Mark L Stone
accept rate: 15%

edited 22 Oct '17, 15:32

Hint: complete the square for \(x_3\).


answered 16 Oct '17, 14:26

Rob%20Pratt's gravatar image

Rob Pratt
accept rate: 28%

Hi @Rob,

I tried that before, which gives: $$x_1 \cdot x_2 \geq (x_3-\frac{1}{2})^2-\frac{1}{4}$$

However, I don't see how it's possible to express this as an SOC. I have tried things like: $$\lVert [x_1 - x_2 - \frac{1}{2},\ 2\cdot (x_3-\frac{1}{2})] \rVert \leq x_{1} + x_{2} + \frac{1}{2}$$ But I don't see any combination of signs in the \(\pm x_{1} \pm x_{2} \pm \frac{1}{2}\) terms that would keep the \((\frac{1}{2})^2\) and \(x_1\cdot x_2\) terms...

Is there any other way of expressing the SOC?

(16 Oct '17, 16:52) Luis Badesa
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 16 Oct '17, 14:15

Seen: 422 times

Last updated: 22 Oct '17, 15:32

OR-Exchange! Your site for questions, answers, and announcements about operations research.