# Maximize quadratic function subject to linear constraints

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 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)?

• 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. – Austin Buchanan May 21 '13 at 20:09
• 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 May 22 '13 at 2:52
• 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 May 22 '13 at 14:48
• @AustinBuchanan, it's called the canonical form of the quadratic form; see e.g. mathworld.wolfram.com/QuadraticForm.html – Yury May 23 '13 at 2:24
• 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 May 23 '13 at 16:53

## 3 Answers

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.

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.

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