How can I simplify this quadratic optimization? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T15:44:26Z http://mathoverflow.net/feeds/question/71293 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/71293/how-can-i-simplify-this-quadratic-optimization How can I simplify this quadratic optimization? Tom Ellis 2011-07-26T06:30:50Z 2011-07-27T06:43:43Z <p>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.</p> <p><a href="http://math.stackexchange.com/questions/53675/how-can-i-simplify-this-quadratic-optimization" rel="nofollow">http://math.stackexchange.com/questions/53675/how-can-i-simplify-this-quadratic-optimization</a></p> <p>I want to minimize $x^t P x + q^t x$ subject to the following constraint:</p> <p>For all $b \in B$, $|x^b| \le C \sum_{b' \in B} |x^{b'}|$</p> <p>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$.</p> <p>The only way I know how to do this is to do $2^{|B|}$ optimizations over the convex cone given by:</p> <p>For all $b \in B$, $x^b \ge 0$ and $x^b \le C \sum_{b' \in B} x^{b'}$</p> <p>and its reflections. Is there a more efficient way to solve this problem?</p> <p>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.)</p> http://mathoverflow.net/questions/71293/how-can-i-simplify-this-quadratic-optimization/71333#71333 Answer by Adam Antonik for How can I simplify this quadratic optimization? Adam Antonik 2011-07-26T17:32:48Z 2011-07-26T17:32:48Z <p>Without further restriction on P, the problem is NP-hard <a href="http://en.wikipedia.org/wiki/Quadratic_programming" rel="nofollow">http://en.wikipedia.org/wiki/Quadratic_programming</a></p> <p>"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.</p> http://mathoverflow.net/questions/71293/how-can-i-simplify-this-quadratic-optimization/71341#71341 Answer by Robert Israel for How can I simplify this quadratic optimization? Robert Israel 2011-07-26T19:07:48Z 2011-07-26T19:07:48Z <p>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. </p>