My Math Forum > Math quadratic program to linear program

 Math General Math Forum - For general math related discussion and news

 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,427 Thanks: 1314 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.

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post sushi Linear Algebra 0 February 9th, 2015 11:46 AM boy129349 Computer Science 3 February 6th, 2012 06:13 AM frosty16 Computer Science 2 January 26th, 2012 01:35 PM davidandersson Geometry 2 August 23rd, 2010 07:28 AM tomw Applied Math 0 March 2nd, 2010 12:13 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top