Solver for Euclidean Norm Squared Constraint Least Squares

Question

I'm looking for a numerical solution to the constrained least squares problem below: $$ \min_\mathbf{x}\|\mathbf{a+Bx}\|^2 ~~\text{s.t}~~\|\mathbf{x}\|^2 \leq \alpha^2$$ where $\mathbf{a} \in \mathbb{C^{M\times 1}}$ and $\mathbf{B} \in \mathbb{C^{M\times N}}$. I'd appreciate it if anyone can point me to a solver, preferably Matlab. I have already looked, but it doesn't look like Matlab has a solver for this.

Answer 1

The problem is given by:

$$ \begin{alignat*}{3} \text{minimize} & \quad & \frac{1}{2} \left\| A x - b \right\|_{2}^{2} \\ \text{subject to} & \quad & {x}^{T} x \leq \alpha \end{alignat*} $$

The Lagrangian is given by:

$$ L \left( x, \lambda \right) = \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + \lambda \left( {x}^{T} x - \alpha \right) $$

The KKT Conditions are given by:

$$ \begin{align*} \nabla L \left( x, \lambda \right) = {A}^{T} \left( A x - b \right) + 2 \lambda x & = 0 && \text{(1) Stationary Point} \\ \lambda \left( {x}^{T} x - \alpha \right) & = 0 && \text{(2) Slackness} \\ {x}^{T} x & \leq \alpha && \text{(3) Primal Feasibility} \\ \lambda & \geq 0 && \text{(4) Dual Feasibility} \end{align*} $$

From (1) one could see that the optimal solution is given by:

$$ \hat{x} = {\left( {A}^{T} A + 2 \lambda I \right)}^{-1} {A}^{T} b $$

Which is basically the solution for Tikhonov Regularization of the Least Squares problem.

Now, from (2) if $ \lambda = 0 $ it means $ {x}^{T} x = 1 $ namely $ \left\| {\left( {A}^{T} A \right)}^{-1} {A}^{T} b \right\|_{2} = 1 $.

So one need to check the Least Squares solution first.
If $ \left\| {\left( {A}^{T} A \right)}^{-1} {A}^{T} b \right\|_{2} \leq \alpha $ then $ \hat{x} = {\left( {A}^{T} A \right)}^{-1} {A}^{T} b $.

Otherwise, one need to find the optimal $ \hat{\lambda} $ such that $ \left\| {\left( {A}^{T} A + 2 \lambda I \right)}^{-1} {A}^{T} b \right\| = \alpha $.

You can see how to solve it in my solution for $ \min_{x^Tx=1} x^TAx-c^Tx$.

Answer 2

Your problem is known as the "trust region subproblem", because it occurs as a subproblem in trust region methods for nonlinear optimization. There are many papers that discuss the numerical challenges of this problem and give specialized algorithms for its solution.

CVX is certainly capable of solving the problem, but one of the specialized algorithms is likely to be much faster.