
Math General Math Forum  For general math related discussion and news 
 LinkBack  Thread Tools  Display Modes 
April 22nd, 2019, 03:25 AM  #1 
Newbie Joined: Apr 2019 From: London Posts: 1 Thanks: 0  quadratic program to linear program
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 skipjack; April 22nd, 2019 at 07:23 AM. 
April 22nd, 2019, 07:34 PM  #2 
Senior Member Joined: Sep 2015 From: USA Posts: 2,529 Thanks: 1389 
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. 

Tags 
linear, program, quadratic 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Linear program  sushi  Linear Algebra  0  February 9th, 2015 11:46 AM 
Fractal Program  boy129349  Computer Science  3  February 6th, 2012 06:13 AM 
linear system program ?  frosty16  Computer Science  2  January 26th, 2012 01:35 PM 
Geometry Program  davidandersson  Geometry  2  August 23rd, 2010 07:28 AM 
Primal/Dual Linear Program problem (Minimum cost critical pa  tomw  Applied Math  0  March 2nd, 2010 12:13 PM 