0
$\begingroup$

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

I am looking for solutions of the following problem in $b$:

$\max \| X b \|_2 \quad\text{subject to} \quad \| b - b_0 \|_2 < a, \| b \|_2 = 1$

where matrix $X$, $a$ and $b_0$ are given. Is this a convex programming problem?

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

2 Answers 2

2

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


Forget about $||b-b_0|| 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||.


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||? If you had $||b-b_0||\leq a$, it would have always solution.)

  • 0
    (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|| 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. – 2013-03-20
0

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

  • 0
    @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. – 2012-10-02