Solver for Euclidean Norm Squared Constraint Least Squares

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