<p>Gurobi has a free academic license: <a href="http://www.gurobi.com/products/licensing-and-pricing/academic-licensing" rel="nofollow">http://www.gurobi.com/products/licensing-and-pricing/academic-licensing</a> However, I don't know how good it is at handling non-convex objective functions.</p>

CC BY-SA 3.0
2013-05-22T00:37:57.870Z
2013-05-22T00:51:58.357Z
2013-05-22T00:51:58.357Z
Grigory Yaroslavtsev
<p>Probably nope (at least for a sum of quadratic variables). Among other things it would probably imply that you can compute the diameter of a symmetric H-polytope in polynomial time. </p>

<p><a href="http://www.ima.umn.edu/preprints/Sept90Series/704.pdf" rel="nofollow">http://www.ima.umn.edu/preprints/Sept90Series/704.pdf</a></p>

CC BY-SA 3.0
2013-05-21T23:11:13.080Z
2013-05-21T23:11:13.080Z
Sariel Har-Peled
<p>It's NP-hard. </p>

<p>Here's a reduction from the feasibility version of Binary Integer Programming (BIP), which is NP-hard. The problem is to decide if there's a feasible solution to the constraints $Ax \leq b$ and $x_i \in \{0,1\}$. It's easy to convert this to a problem with the constraints $Ax \leq b$ and $x_i \in \{-1,1\}$.</p>

<p>Now consider the following optimization problem: 
$\max \sum_i x_i^2$ subject to the constraints $Ax \leq b$ and $-1 \leq x_i \leq 1$ for all $i$.</p>

<p>This problem has objective value $n$ (the total number of variables $x_i$) if and only if the original BIP problem was feasible.</p>

CC BY-SA 3.0
2013-05-22T00:52:39.537Z
2013-05-22T01:21:39.107Z
2013-05-22T01:21:39.107Z
Robin Kothari
<p>Can one maximize $\sum_i c_i x_i^2$ where the $c_i$ are constants (possibly negative), subject to linear constraints over the $x_i$?</p>

<p><a href="http://link.springer.com/article/10.1007/BF00120662" rel="nofollow">This paper</a> seems to come close to answering "no."  They show it is NP-hard for target functions $x_1 - x^2_2$.  However they have $x_1$ which is not squared, and from the two pages I can access online I can't understand if that's critical or not.</p>

<p>Bonus question: Is there a free software that can be tried to solve these problems (possibly heuristically)?</p>

CC BY-SA 3.0
2013-05-21T20:09:33.503Z
I am not sure about the case where the quadratic terms take the form $x_i^2$. However, in the case that you have $x_i x_j$ quadratic terms it is NP-hard. For example, see the continuous formulation for maximum clique given by [Motzkin and Straus](http://dcg.epfl.ch/files/content/sites/dcg/files/Courses/Graph%20Theory%202011/motzkin_straus_paper.pdf).
Austin Buchanan
CC BY-SA 3.0
2013-05-22T02:52:33.850Z
The problem is as general as the problem of maximizing a general quadratic form $x^T A x$ subject to linear constraints since every quadratic form can be brought to a diagonal form. The problem is NP-hard.
Yury
CC BY-SA 3.0
2013-05-22T14:48:44.033Z
Thanks.  I had forgotten that over the reals (unlike GF(2)) that's what you get.  I think this can be an answer, too, but I'll accept Robin's.
Manu
CC BY-SA 3.0
2013-05-22T21:02:37.773Z
@Yury I am not aware of such a transformation. Could you give a reference?
Austin Buchanan
CC BY-SA 3.0
2013-05-23T02:24:34.930Z
@AustinBuchanan, it's called the canonical form of the quadratic form; see e.g. http://mathworld.wolfram.com/QuadraticForm.html
Yury
CC BY-SA 3.0
2013-05-23T16:53:24.573Z
Various software packages are available for non-linear optimization (to find a local optimum). Typically they are based on solvers for quadratic programming which is studied heavily. SNOPT is one that is reasonably well-known.
Chandra Chekuri
<optimization><quadratic>
Maximize quadratic function subject to linear constraints
Manu
# Maximize quadratic function subject to linear constraints

(Asked by: username_0 on 2013-05-21)

Can one maximize $\sum\_i c\_i x\_i^2$ where the $c\_i$ are constants (possibly negative), subject to linear constraints over the $x\_i$?

[This paper](http://link.springer.com/article/10.1007/BF00120662) seems to come close to answering "no." They show it is NP-hard for target functions $x\_1 - x^2\_2$. However they have $x\_1$ which is not squared, and from the two pages I can access online I can't understand if that's critical or not.

Bonus question: Is there a free software that can be tried to solve these problems (possibly heuristically)?

**Tags:** optimization, quadratic

> **Comments:**
> **username_1**: I am not sure about the case where the quadratic terms take the form $x_i^2$. However, in the case that you have $x_i x_j$ quadratic terms it is NP-hard. For example, see the continuous formulation for maximum clique given by [Motzkin and Straus](http://dcg.epfl.ch/files/content/sites/dcg/files/Courses/Graph%20Theory%202011/motzkin_straus_paper.pdf).  
> **username_2**: The problem is as general as the problem of maximizing a general quadratic form $x^T A x$ subject to linear constraints since every quadratic form can be brought to a diagonal form. The problem is NP-hard.  
> **username_0**: Thanks.  I had forgotten that over the reals (unlike GF(2)) that's what you get.  I think this can be an answer, too, but I'll accept Robin's.  
> **username_1**: @username_2 I am not aware of such a transformation. Could you give a reference?  
> **username_2**: @AustinBuchanan, it's called the canonical form of the quadratic form; see e.g. http://mathworld.wolfram.com/QuadraticForm.html  
> **username_3**: Various software packages are available for non-linear optimization (to find a local optimum). Typically they are based on solvers for quadratic programming which is studied heavily. SNOPT is one that is reasonably well-known.  

---

## 3 answers

### Answer by username_6 on 2013-05-22. Score: 7 | Accepted answer

It's NP-hard.

Here's a reduction from the feasibility version of Binary Integer Programming (BIP), which is NP-hard. The problem is to decide if there's a feasible solution to the constraints $Ax \leq b$ and $x\_i \in \{0,1\}$. It's easy to convert this to a problem with the constraints $Ax \leq b$ and $x\_i \in \{-1,1\}$.

Now consider the following optimization problem:
$\max \sum\_i x\_i^2$ subject to the constraints $Ax \leq b$ and $-1 \leq x\_i \leq 1$ for all $i$.

This problem has objective value $n$ (the total number of variables $x\_i$) if and only if the original BIP problem was feasible.


---

### Answer by username_4 on 2013-05-22. Score: 2

Gurobi has a free academic license: <http://www.gurobi.com/products/licensing-and-pricing/academic-licensing> However, I don't know how good it is at handling non-convex objective functions.


---

### Answer by username_5 on 2013-05-21. Score: 1

Probably nope (at least for a sum of quadratic variables). Among other things it would probably imply that you can compute the diameter of a symmetric H-polytope in polynomial time.

<http://www.ima.umn.edu/preprints/Sept90Series/704.pdf>


---

