Return to Question

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.

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

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

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.

http://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. (Perhaps an approximate solution is much easier to find. Help with that would be appreciated too.)

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.

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

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.

http://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. (If necessary it could perhaps be assumed that $P$ is close to diagonal and $q$ is close to $0$).

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

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.

http://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.  (Perhaps an approximate solution is much easier to find. Help with that would be appreciated too.)