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.

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!

share|improve this question
add comment

2 Answers

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

share|improve this answer
    
+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
add comment

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

share|improve this answer
2  
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
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.