How can I simplify this quadratic optimization? - MathOverflow

How can I simplify this quadratic optimization?

2011-07-26T06:30:50Z

I have no experience in the field of optimization, so I have no idea how hard or naive it is. I got no response on math.stackexchange so I am posting it here, though I doubt it is research-level.

http://math.stackexchange.com/questions/53675/how-can-i-simplify-this-quadratic-optimization

I want to minimize $x^t P x + q^t x$ subject to the following constraint:

For all $b \in B$, $|x^b| \le C \sum_{b' \in B} |x^{b'}|$

where $B = \{1, ..., n\}$ and $x^b$ is the $b$th component of the $n$-dimensional column vector $x$. $C$ is some positive constant which, to avoid triviality, should satisfy $1/|B| \le C \le 1$.

The only way I know how to do this is to do $2^{|B|}$ optimizations over the convex cone given by:

For all $b \in B$, $x^b \ge 0$ and $x^b \le C \sum_{b' \in B} x^{b'}$

and its reflections. Is there a more efficient way to solve this problem?

For my purposes let's say $C = 1/5$ and $n = 100$. I'm not sure I have much choice in the structure of $P$ and $q$, so an efficient solution for general $P$ and $q$ is desirable. [EDIT: $P$ is positive semidefinite] (Perhaps an approximate solution is much easier to find. Help with that would be appreciated too.)

Answer by Adam Antonik for How can I simplify this quadratic optimization?

2011-07-26T17:32:48Z

Without further restriction on P, the problem is NP-hard http://en.wikipedia.org/wiki/Quadratic_programming

"For positive definite [P], the ellipsoid method solves the problem in polynomial time. If, on the other hand, if [P] is indefinite, then the problem is NP-hard. In fact, even if [P] has only one negative eigenvalue, the problem is NP-hard.

Answer by Robert Israel for How can I simplify this quadratic optimization?

2011-07-26T19:07:48Z

Your constraint is non-convex, there's no getting around that (so you can't just replace it with some linear constraints, say). But what you might try is this: start by minimizing the objective without the constraint. If the optimal solution satisfies the constraint, good; otherwise, see what the signs are in this solution and solve over the convex cone with the version of your constraint corresponding to those signs. The result might not be optimal, but at least you'll have a bound. Then you might try varying some of the signs one-by-one to see if you can get improvements.