linearize the quadratic constraint

1.5k Views Asked by At

I solve the quadratic problem. There is one constraint of this form:

$$\sum_{i=1}^n \sum_{j=1}^nc_{ij} x_i x_j \le \mathrm{GE} $$

where $x$ is a continuous variable, $c$ is coefficient matrix and $\mathrm{GE}$ is a vector of the right-hand side bounds.

In some special case of data, there is problem of solving this because the input matrix is not positive-definite. I would like to form the model for general using (for any type of data) so I decided to linearize this constraint. Can you give me the advice how to do it?

1

There are 1 best solutions below

1
On

As suggested in the AIMMS Guide Optimization Modeling (cf. page 85), you could introduce continuous variables:

$$\begin{aligned} y_i &= \frac{1}{2}(x_i + x_j) \\ y_j &= \frac{1}{2}(x_i - x_j) \end{aligned}$$

Now the product term $x_ix_j$ can be replaced by

$$y_i^2 - y_j^2$$

I am not sure how to deal with the fact that you have to linearize more than one product at the same time. Every $x_i$ occurs in various products. Therefore, the approach might be of limited use for you.