My Math Forum  

Go Back   My Math Forum > Math Forums > Math

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


Reply
 
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.
Craig1 is offline  
 
April 22nd, 2019, 07:34 PM   #2
Senior Member
 
romsek's Avatar
 
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.
romsek is offline  
Reply

  My Math Forum > Math Forums > Math

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





Copyright © 2019 My Math Forum. All rights reserved.