How to solve this quadratically constrained quadratic programming problem?

Question

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!

Answer 1

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

Answer 2

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