Could you please shed some lights on this? (Not a homework problem)

I am looking for solutions to solve the following problem:

$$\text{max } || X b || \text{ s.t. } || b - b_0 || < a, || b || = 1$$

Here the norms are 2-norms.

$X$ is a matrix, $b_0$ and $a$ are parameters. All of $X$, $a$ and $b_0$ are given.

I would like to solve for the vector $b$.

Is this a convex programming problem?

I am thinking of using the Lagrange method to solve for it... I am guessing that after I make it into the standard Lagrange form, maybe I could find closed-form solutions?

Thank you!

-

Method of Lagrange multipliers gives that only eigen vectors of $X^TX$ can be solution to your problem.

Forget about $||b-b_0||<a$ for now

$\text{max} ||Xb||^2, s.t. ||b||^2=1$

Lagrange multipliers gives

$\text{grad}||Xb||^2 = \lambda \text{grad}||b||^2$

$2X^TXb=\lambda 2b$, so b has to be eigen vector of $X^TX$

So you get suspected points $b_1,b_2,..b_k$, which are eigen vectors of $X^TX$ and $||b_i-b_0||<a$.

But there can be maxima on boundary i.e. on $\{b: ||b||=1, ||b-b_0||=a\}$. So you have to do Lagrange multipliers once more. So you have to solve $\text{grad}||Xb||^2 = \lambda_1 \text{grad}||b||^2 + \lambda_2 \text{grad}( ||b-b_0||^2-a^2)$. You get suspected points $c_1,...,c_l$. Now you have to find at which point from $b_1,..,b_k,c_1,..,c_l$ attains $f(b)=||Xb||$ its maximum. If it is point $b_i$ tha you are ok and solution exists. If it is $c_i$ than you are screwed.

(Is there really $||b-b_0||<a$? If you had $||b-b_0||\leq a$, it would have always solution.)

-
+1. Nice! (1) How do $||b−b_0||<a$ and $||b−b_0||\leq a$ make differences? (2) If there is no eigen vector in $||b−b_0||\leq a$, why there is no solution to the original problem? – steveO Mar 20 '13 at 13:12
(1) because $\{b:||b||=1 \} \cap\{ b:||b−b_0||\leq a \}$ is compact(every continuous function on compact attains its maximum) and that is answer to (2) as well. But I found mistake in my answer. The biggest eigen vector in $||b-b_0||<a$ does not have to be solution. There can be even bigger value on boundary i.e. on $\{b:||b-b_0||=a, ||b||=1\}$ is so than again there is no solution. – tom Mar 20 '13 at 13:50

It is convex (a convex function subject to a convex set). Consider finding its dual by KKT technique.

-
How is this convex? $||b||=1$ does not describe a convex set. – copper.hat Jul 9 '12 at 7:10
If $X$ is a matrix, then $X\lambda b = \lambda Xb$ for scalars $\lambda$. Hence we have that taking the max in $\|b\| \leq 1$ is the same as taking the max in $\|b\| = 1$. But I agree with @copperhat that this info should be given in the answer. – Willie Wong Jul 9 '12 at 8:32
@copper.hat: Sorry, it is not convex. I thought it is less than or equal not equality. However, it can be relaxed as Willie Wong suggested. – Taha Oct 2 '12 at 5:59