Least squares with a quadratic inequality constraint

Question

Is there a closed form solution for the following least squares problem: $$ \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}}$.

Answer 1

It depends.

Consider the unconstrained least squares problem

$$ \min_\mathbf{x}\|\mathbf{a+Bx}\|^2. $$

This problem has the solution $\mathbf{x}^\star = - (\mathbf{B}^H\mathbf{B})^{-1}\mathbf{B}^H\mathbf{a} $. It is clear that $\mathbf{x}^\star $ is also the solution to your problem if $\|\mathbf{x}^\star\|^2 \leq \alpha^2$. In this case, you have an analytical solution.

However, if $\|\mathbf{x}^\star\|^2 > \alpha^2$, you have to consider the constrained problem

$$ \min_\mathbf{x}\|\mathbf{a+Bx}\|^2 + \lambda \|\mathbf{x}\|^2, $$ where $\lambda >0 $ is the Lagrange-Multiplier. This problem has the solution

$$\mathbf{x}^\star = - (\mathbf{B}^H\mathbf{B} + \lambda \mathbf{I})^{-1}\mathbf{B}^H\mathbf{a}$$

For the proper Lagrange-Multiplier $\lambda$, $\|\mathbf{x}^\star\|^2 = \alpha^2$ holds true. However, there is no analytical way to determine $\lambda$ which can be found by using bi-section search.