# Approach to handle a quadratic constraint xy <= z

I have non-linear constraints like

$x_1x_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?

• That is a bilinear constraint, which is non-convex. $x_1x_2$ is indefinite. – Mark L. Stone Dec 24 '16 at 17:44
• 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 Dec 24 '16 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 Dec 24 '16 at 18:45
• What's the dimension (number of variables) of your problem? How many bilinear constraints does your problem have? This might be an easy problem for a global optimizer, such as BARON or BMIBNB iin YALMIP, depending on how many bilinear constraints there are. – Mark L. Stone Dec 24 '16 at 21:00
• Hold your horses. The exponential equality is not convex. The relaxation $exp(z_i) \le x_i$ is convex, but might not get the job done. – Mark L. Stone Dec 27 '16 at 22:59

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 Dec 30 '16 at 3:30

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.

• You are trying to to convex conic alchemy. The exponential equality is not convex. The relaxation $exp(z_i) \le x_i$ is convex, but might not get the job done. – Mark L. Stone Dec 27 '16 at 22:58
• @Mark L. Stone Yes, of course, I was thinking about the inequality. Thanks for the note. :) – DDCh Dec 30 '16 at 1:38