[Math] Linear Equality Constrained Least Squares

convex optimizationleast squaresoptimizationregressionregression analysis

Suppose y is a random variable.

$$y=X \beta + \varepsilon,$$
$$ \varepsilon \sim N(0,I_n)$$

$$(y : n\times 1,\, X:n\times p, \,\beta:p\times1 \text{ matrix} )$$
The ordinary least square estimator minimizing $$(y-X\beta)'(y-X\beta)$$ is given by $$\hat\beta=(X'X)^{-1}X'y$$

The question is,
when there is a constraints on beta given by
$$T\beta=c$$

How can I get the new least square estimator under the constraints?

The answer is
$$\hat\beta+(X'X)^{-1}T'[T(X'X)^{-1}T]^{-1}(c-T\hat\beta)$$
(it is on my book)
but I don't know how to get it.

Best Answer

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 = 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} $$

Related Question