I am taking a Theory of Linear Models class and got the following assignment:
Solve the Least Squares Probem using Lagrange Multipliers.
We are in the 3rd week of this class so we have only covered the basics. I don't have much experience in this field and the problem statement is not too elaborate so I need some perspective. I have researched and all the information I can find is on Constrained Linear Models, some have what they call "linear constraints", like here:
Then again, it says "When we compare different models". Am I supposed to solve a problem with a linear constraint or is that something completely different? Any tips to get me started would be highly appreciated.
Best Answer
Given
$$\begin{array}{ll} \text{minimize} & \| \mathrm A \mathrm x - \mathrm b \|_2^2\\ \text{subject to} & \mathrm C \mathrm x = \mathrm d\end{array}$$
we define the Lagrangian
$$\mathcal L (\mathrm x, \lambda) := \frac 12 \| \mathrm A \mathrm x - \mathrm b \|_2^2 + \lambda^{\top} \left( \mathrm C \mathrm x - \mathrm d \right)$$
Taking the partial derivatives and finding where they vanish, we obtain the following linear system
$$\begin{bmatrix} \mathrm A^{\top} \mathrm A & \mathrm C^{\top}\\ \mathrm C & \mathrm O\end{bmatrix} \begin{bmatrix} \mathrm x\\ \lambda\end{bmatrix} = \begin{bmatrix} \mathrm A^{\top} \mathrm b\\ \mathrm d\end{bmatrix}$$