2
$\begingroup$

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?

Improve this question
$\endgroup$
19
  • 2
    $\begingroup$ That is a bilinear constraint, which is non-convex. $x_1x_2$ is indefinite. $\endgroup$
    – Mark L. Stone
    Dec 24 '16 at 17:44
  • 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
    Dec 24 '16 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
    Dec 24 '16 at 18:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mark L. Stone
    Dec 24 '16 at 21:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mark L. Stone
    Dec 27 '16 at 22:59
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}$.

Improve this answer
$\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
    Dec 30 '16 at 3:30
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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mark L. Stone
    Dec 27 '16 at 22:58
  • $\begingroup$ @Mark L. Stone Yes, of course, I was thinking about the inequality. Thanks for the note. :) $\endgroup$
    – DDCh
    Dec 30 '16 at 1:38

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.