Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

(Perhaps an approximate solution is much easier to find. Help with that would be appreciated too.)

share|improve this question
    
A useful trick for absolute values is to introduce a new variable $y$ with $-y<x<y$ and $y=>0$ where you also minimze $y$. This makes sure that y=|x| (after minimization). So you should be able to convert all your inequalities involving absolute values into linear inequalities in this way (introducing new variables in the described way and making sure you minimize them with your $q^tx$). And minimizing a quadratic function over linear inequalites is known as 'quadratic programming' and is solvable in polynomial time with interior point methods. –  Peter Sheldrick Jul 25 '11 at 17:13
    
Peter, can you explain how to ensure $y$ is minimized by using the $q^t x$? It's the whole function $q^t x$ that's minimized so I don't understand you can ensure that $y$ actually comes out as $|x|$. –  Tom Ellis Jul 26 '11 at 8:16
    
This looks suspiciously like portfolio allocation with a constraint that the portfolio can't be dominated by any one asset. You might have more success with a constraint that's not as easy to interpret, but is more mathematically tractable. For example, it's easy to solve the equivalent problem with $|x^b|<k$ $\forall b$ (use convex optimization) and even easier if you have a penalty term of the form $\lambda\| x\|^2$ (use calculus). –  Chris Taylor Jul 28 '12 at 12:49
add comment

1 Answer

Your constraints are that $-C \|x\|_1 \leq x \leq C \|x\|_1$ componentwise. You can transform the $\|x\|_1$ by introducing new variables $x_+$ and $x_-$, both $\geq 0$ and splitting $x = x_+ - x_-$. With these new variables, $\|x\|_1 = \sum_{b \in B} (x_+^b + x_-^b)$. So your constraints become $$ -C \sum_{b \in B} (x_+^b + x_-^b) \leq x \leq C \sum_{b \in B} (x_+^b + x_-^b), $$ $$ x = x_+ - x_-, \quad (x_+, x_-) \geq 0. $$ Now your problem is a standard quadratic program.

share|improve this answer
    
Unfortunately not, Dominique. This does not constrain one of $x_+$ and $x_-$ to be zero. –  Tom Ellis Nov 27 '11 at 21:19
add comment

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.