Linear Least Square Optimization with Linear Equality Constraints What is the exact solution $x_{n \times 1}$ of the following constrained optimization problem
\begin{align*}
&\min \|A x - b\|^2 \\
s.t.& C x = 0
\end{align*}
where $A$ is full column rank $m \times n$ matrix ($m>n$); $b$ is $m \times 1$ matrix; $C$ is full row rank $1 \times n$ matrix?
 A: The Lagragian is the following:
$$
L = \sum \limits_{i = 1}^{m}(\sum \limits_{j = 1}^{2}a_{ij}x_{j} - b_{i})^{2} + \lambda \sum \limits_{j = 1}^{n}c_{i}x_{i}
$$
$$
\frac{\partial L}{\partial x_{k}} = 2 \sum \limits_{j = 1}^{n}(\sum \limits_{i = 1}^{n}a_{ij}a_{ik})x_{j} - 2 n \sum \limits_{i = 1}^{m}b_{i} a_{ik} + \lambda c_{k} = 0
$$
There are $n + 1$ equations and $n + 1$ unknowns.
A: The problem is given by:
$$
\begin{alignat*}{3}
\arg \min_{x} & \quad & \frac{1}{2} \left\| A x - b \right\|_{2}^{2} \\
\text{subject to} & \quad & C x = \boldsymbol{0}
\end{alignat*}
$$
The Lagrangian is given by:
$$ L \left( x, \nu \right) = \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + {\nu}^{T} C x $$
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 \\ 
\boldsymbol{0}
\end{bmatrix} $$
Now all needed is to solve the above with any Linear System Solver.
A: $
\def\LR#1{\left(#1\right)}
\def\qiq{\quad\implies\quad}
$Since the constraint is linear it has an explicit solution in terms of the nullspace projector
$$\eqalign{
P &= I-C^+C \qiq P^T=P=P^2 \\
}$$
$$\eqalign{
Cx &= 0 \qiq x = Pu
}$$
where a new unconstrained vector variable $u$ has been introduced.
In terms of $u,\,$ the objective function is likewise unconstrained
$$\eqalign{
\phi &= \|APu-b\|^2 \\
}$$
Thus it can be immediately solved using a pseudoinverse
$$\eqalign{
u &= \LR{AP}^+b \qiq
x = P\LR{AP}^+b = \LR{I-C^+C}\LR{A-AC^+C}^+b \\
}$$
${\bf NB\!:}\;$ This solution remains valid when $C$ is an arbitrary matrix, not simply a vector.
