# How to handle the quadratic constraint $x y \leq z$?

I have a quadratic constraint of the form

$$x_1 x_2 \leq x_3$$

where $$x_1, x_2, x_3 \geq 0$$. The objective is linear, and all other constraints are linear, too. I know that I can transform the product as

$$y_1=\frac{1}{2}(x_1+x_2)$$

$$y_2=\frac{1}{2}(x_1−x_2)$$

$$y_1^2−y_2^2\leq x_3$$

But when it comes to the last constraint, it is not convex (matrix is not PSD), and thus not suitable for commercial solvers like CPLEX and Gurobi (as far as I know). Moreover, they are not conic quadratic representable. At least I don't know how to reformulate them, or to find a suitable approximation ("good for practical purposes"). Now, my question.

Is there an efficient (to some degree) approach to deal with these kind of constraints?

I am asking this because they look quite simple and the constraint expressions are the difference of convex functions $$y_1^2−(y_2^2+x_3)$$ (the sum of two convex functions on different domains is convex).

Maybe some relaxation technique has been proven to be useful? Convexification? In other words, how to circumvent this?

• I know it is not convex. But what to do with it?
– DDCh
Commented Dec 24, 2016 at 17:45
• I would consider the case in which the product constraint is tight, and use the equality $x_1 x_2 = x_3$ to eliminate one variable from the problem.
– hardmath
Commented Dec 24, 2016 at 18:17
• That's more elaborate than what I was thinking, but that is perhaps better. I was just thinking that if the constraint is not tight (equality), then you can drop it and solve the remaining linear program (which I'm sure you already did).
– hardmath
Commented Dec 24, 2016 at 18:45
• Are you referring to slavko's answer at or-exchange.org/questions/14687/… , which is the same as the given answer below by you? You should give "credit" to that answer. Commented Dec 27, 2016 at 23:03
• I think both forums would say that you shouldn't cross-post at the same time, and if you do, you should provide a link to any other posting on the same or similar question. Commented Dec 30, 2016 at 1:57

If this is the only relevant part of your problem, you can write this as a semidefinite program. Since $x_1, x_2$ do not appear individually you can treat it as a square of a positive number then your problem is the feasibility of

$$\begin{pmatrix} x_3 & y & \\ y & 1 & \\ && y \\ \end{pmatrix} \succeq 0$$ where $y = \sqrt{x_1x_2}$.

• Yes, you are right, they do not appear individually in the constraints, but what if they appear in linear objective? My first thought was to lift the program into a higher dimension space, too (your approach is better, BTW). Then I saw that I could use reformulation-linearisation techniques (RLT) to strengthen the relaxation. But somehow, to me, it just looks like one can do much more. Like there is a trick that I can't see. Maybe my hunch is wrong about this (I am not an expert), but I had to ask.
– DDCh
Commented Dec 30, 2016 at 3:30

To me it looks you are dealing with a standard Geometric Program (GP) which can be handled easily by commercial solvers (see e.g. https://www.cvxpy.org/tutorial/dgp/index.html)

As I said in the comment, I got a new hint: https://www.or-exchange.org/questions/14687/approach-to-resolve-the-issue-with-a-non-linear-constraint-xy-z.

The bi-linear constraints can be attacked with the logarithm function. Therefore, we can introduce new variables $z_i = \ln(x_i)$ and our constraints will become

$z_1 + z_2 \leq z_3$.

Of course, we have to include the additional constraints, too. Particularly, those that are representing the connection of $z_i$ and $x_i$

$\exp(z_i) = x_i$.

But the exponential function is conic quadratic representable for practical purposes.

• @Mark L. Stone Yes, of course, I was thinking about the inequality. Thanks for the note. :)
– DDCh
Commented Dec 30, 2016 at 1:38