Linear Least Squares with Linear Equality Constraints: $ \arg \min_{x} {\left\| x - {x}_{0} \right\|}_{2}^{2} $ s. t. $ A x = b $

Question

Let $A\in \mathbb R^{m×n}, b \in \mathbb R^m$ with $m \leq n$, $\operatorname{rank} A = m$ and $x_0 \in \mathbb R^n$. Consider the problem : $$\arg \min\|x-x_0\|² \quad\text{s.t. }Ax = b$$

How can I solve this, please? I was thinking about using the least square solution to $Ax=b$ minimizing $\|x\|$ but I'm not sure.

Thank you for your help.

Answer 1

Let $y=x-x_0$; then $Ay=b-Ax_0$. If you use least squares for this transformed system $\|y\|=\|x-x_0\|$ will be minimized. After that you need to add $x_0$ to $y^*$ to get the solution $x^*$.

Answer 2

The general problem is given by (Linear Least Squares with Linear Equality Constraints):

$$ \begin{alignat*}{3} \arg \min_{x} & \quad & \frac{1}{2} \left\| A x - b \right\|_{2}^{2} \\ \text{subject to} & \quad & C x = d \end{alignat*} $$

The Lagrangian is given by:

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

From KKT Conditions the optimal values of $ \hat{x}, \hat{\nu} $ obeys:

$$ \begin{bmatrix} {A}^{T} A & {C}^{T} \\ C & 0 \end{bmatrix} \begin{bmatrix} \hat{x} \\ \hat{\nu} \end{bmatrix} = \begin{bmatrix} {A}^{T} b \\ d \end{bmatrix} $$

Now all needed is to solve the above with any Linear System Solver.

To adapt this into your problem we can set $ A = I $ and solve.