# 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?

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.

• Just to make it clear: $n$ equations come from $\frac{\partial L}{\partial x_k}$, the last is the constraint $Cx=0$. – AndreaCassioli Jul 11 '14 at 11:23

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.

• What happens in the case that the constraints are of the form: Cx <= 0 ?? How it affects the solution proposed here? – noob-mathematician Sep 12 '18 at 15:44
• @noob-mathematician, Please open a question and link here. I will try to solve it. – Royi Sep 12 '18 at 16:54
• – Royi Sep 12 '18 at 18:25
• math.stackexchange.com/questions/2915740/… – noob-mathematician Sep 13 '18 at 15:28