Linearization Technique

515 Views Asked by At

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.

1

There are 1 best solutions below

2
On

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.