My Math Forum  

Go Back   My Math Forum > Math Forums > Math

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

LinkBack Thread Tools Display Modes
April 22nd, 2019, 03:25 AM   #1
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

Last edited by skipjack; April 22nd, 2019 at 07:23 AM.
Craig1 is offline  
April 22nd, 2019, 07:34 PM   #2
Senior Member
romsek's Avatar
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.
romsek is online now  

  My Math Forum > Math Forums > Math

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

Copyright © 2019 My Math Forum. All rights reserved.