# quadratic program to linear program

#### Craig1

Hi Community,

I am new in this forum and I hope that I can help you as well as you can help me to solve my problems. I have a quadratic program, where I want to minimize:

$$\displaystyle \sum_{i=1}^n \sum_{j=1}^n x_i x_j a_{i,j}$$

and every $$\displaystyle x_i \in \{0,1\}$$So all in all it is a quadratic problem of the form: minimize
$$\displaystyle x^T*A*x$$
where x is a vector and A a matrix. How can I bring that to a linear problem?
I had one idea to define another variable $$\displaystyle y_{i,j} := x_i * x_j$$ and to make some new constraints like
$$\displaystyle y_{i,j} \geq 0 ,\\ y_{i,j} \leq x_i ,\\ y_{i,j} \leq x_j$$
But this is not complete and I have no idea whether this is working.
How can I define a linear problem of a quadratic problem?
Thank you very much for your help.

Best regards
Craig

Last edited by a moderator:

#### romsek

Math Team
I would think that to minimize $x^T A x$ you would set

$\dfrac{d}{dx}\left(x^T A x\right) = 0$

$(A + A^T)x = 0$

this last equation is linear. Maybe this is what you are after

Solving this just gets you a critical point. It may be a minimum or a maximum or in multiple dimensions like this it may be neither.