2
$\begingroup$

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.

https://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.)

Improve this question
$\endgroup$
5
  • 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
    Commented Jul 26, 2011 at 7:00
  • $\begingroup$ @Ricky: no particular reason. That's just the notation that I happened to settle on. $\endgroup$
    – Tom Ellis
    Commented Jul 26, 2011 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
    Commented Jul 26, 2011 at 10:03
  • $\begingroup$ So is $P$ an arbitrary symmetric matrix, or it is semidefinite? $\endgroup$
    – Suvrit
    Commented Jul 26, 2011 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
    Commented Jul 27, 2011 at 6:42

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, I've edited the statemet to say that $P$ is positive semidefinite. $\endgroup$
    – Tom Ellis
    Commented Jul 27, 2011 at 6:44
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks Robert. I can indeed probe some small part of the search space in reasonable time. $\endgroup$
    – Tom Ellis
    Commented Jul 27, 2011 at 6:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .