current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite

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

share|improve this question
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. –  Austin Buchanan May 21 '13 at 20:09
4  
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. –  Emanuele Viola May 22 '13 at 14:48
2  
@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
1  
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 3

up vote 7 down vote accepted

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.

share|improve this answer
up vote 2 down vote

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.

share|improve this answer
up vote 1 down vote

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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