-1

I deal with a Mixed Integer Quadratic problem in my thesis. The objective function is quadratic and nonconvex with linear constraints. The objective function contains several terms which are the product of two continuous variables and these terms in the objective function makes it nonconvex. The objective function has the following pattern: $$\sum x_i^2 -\sum x_i y_i+ \sum z_j$$

I want to know about the methods for linearization.

MrYouMath
  • 15,833
m. bank
  • 19
  • Your question is not precise enough. Edit your question, what is the index of summation? What do you mean by linearization methods? Just invest more time into your question formulation such that users on MathStackExchange invest their time to answer your question. – MrYouMath Sep 24 '17 at 09:21

1 Answers1

0

It cannot be linearized.

If you want to stay in the LP-world, the best you can do is to approximate it. Write $x_i^2-x_iy_i$ as $(x_i-y_i/2)^2 - y_i^2/4$ and introduce a new variable and equality constraint $z_i = (x_i-y_i/2)$, and approximate the quadratic terms $z_i^2$ and $y_i^2$ using piecewise affine approximators.

If you work with a QP solver, you can keep the convex part of the quadratic objective of course.

Johan Löfberg
  • 9,497
  • 1
  • 15
  • 15
  • thanks for your answer. is it possible to explain piecewise affine approximators . or introduce a reference – m. bank Sep 24 '17 at 20:19
  • Assuming you are using a good LP solver, you should look into (google) the general area of piecewise affine approximations using SOS2 constructs. – Johan Löfberg Sep 25 '17 at 05:45