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

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

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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.