quadratic program to linear program

Apr 2019
1
0
London
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
Sep 2015
2,969
1,676
USA
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.