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.


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

  • 1
    $\begingroup$ Is there a reason for $\sum_{b'\in B}$ as opposed to $\displaystyle\sum_{b=1}^n$ ? (which you would get with \displaystyle\sum_{b=1}^n ) $\endgroup$ – user5810 Jul 26 '11 at 7:00
  • $\begingroup$ @Ricky: no particular reason. That's just the notation that I happened to settle on. $\endgroup$ – Tom Ellis Jul 26 '11 at 8:05
  • $\begingroup$ I have thought about this some more. An algorithm solving my problem would be similar to an algorithm solving the Closest Vector Problem, which I believe is known to be NP-hard, so perhaps a subexponential algorithm is asking too much! (Still, I don't have experience in this area so a confirmation of this point from someone knowledgeable would be welcome!). $\endgroup$ – Tom Ellis Jul 26 '11 at 10:03
  • $\begingroup$ So is $P$ an arbitrary symmetric matrix, or it is semidefinite? $\endgroup$ – Suvrit Jul 26 '11 at 17:46
  • $\begingroup$ @Suvrit: All the eigenvalues are positive, although in the case I'm considering the smallest are $10^7$ times smaller than the largest. $\endgroup$ – Tom Ellis Jul 27 '11 at 6:42

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.

  • $\begingroup$ Thanks, I've edited the statemet to say that $P$ is positive semidefinite. $\endgroup$ – Tom Ellis Jul 27 '11 at 6:44

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.

  • $\begingroup$ Thanks Robert. I can indeed probe some small part of the search space in reasonable time. $\endgroup$ – Tom Ellis Jul 27 '11 at 6:46

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.