2
$\begingroup$

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?

$\endgroup$
16
  • $\begingroup$ I know it is not convex. But what to do with it? $\endgroup$
    – DDCh
    Commented Dec 24, 2016 at 17:45
  • 2
    $\begingroup$ 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. $\endgroup$
    – hardmath
    Commented Dec 24, 2016 at 18:17
  • 1
    $\begingroup$ 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). $\endgroup$
    – hardmath
    Commented Dec 24, 2016 at 18:45
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Dec 27, 2016 at 23:03
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Dec 30, 2016 at 1:57

3 Answers 3

1
$\begingroup$

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}$.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – DDCh
    Commented Dec 30, 2016 at 3:30
1
$\begingroup$

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)

$\endgroup$
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.