User Name Remember Me? Password

 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,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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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

Copyright © 2019 My Math Forum. All rights reserved.      