2
$\begingroup$

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

  • 0
    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| $\forall b$ (use convex optimization) and even easier if you have a penalty term of the form $\lambda\| x\|^2$ (use calculus).2012-07-28

1 Answers 1

1

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. $ In order to force one of $x_-$ or $x_+$ to be zero, you could add the complementarity constraint $ x_- \cdot x_+ = 0 \quad \text{(or $\leq 0$)}. $ The result is a quadratic program with complementarity constraints (QPCC or QPEC). There are various approaches to solve it, including certain interior-point methods. You need a specialized method to solve the problem in this form because it is degenerate, i.e., it does not satisfy the Mangasarian-Fromowitz constraint qualification condition.

  • 0
    @TomEllis Sorry about this omission. I updated my answer.2017-05-07