🚀 go-pugleaf

ngo1@quads.uchicago.edu (hang-yue  ngo) writes:

>I have a problem:  minimize (Y - Xb)'(Y - Xb) with respect to b
> subject to Cb = d.  b  is a px1 vector and C is a qxp matrix.
> The matrix X may not be full rank (i.e., rank(X) = r < p).
> 
> A solution is given in Kennedy and Gentle, the solution is

>  b = (X'X + C'C)^{-1} X'Y.

> Can anyone show me other methods/solutions to this constrained
> LS problem?  Thanks in advance.

If you look in Kennedy and Gentle again you will see that this
"solution" is in fact a solution only for the case where d = 0.

One intuitive solution to the general problem can be obtained by
noting that Cb = d if and only if b = Az + e for some z in R^(p-q),
where A is any px(p-q) matrix of rank p-q for which CA = 0, and e is
any particular solution to the equation Ce = d.  So the constrained
problem is equivalent to the unconstrained problem:

	min (Y - Xe - XAz)'(Y - Xe - XAz)
	 z

which has solution

	z = (A'X'XA)^(-1)A'X'(Y - Xe)

assuming that the inverse exists.  (If not, then there is no unique
solution to the original problem, and you need some additional
criteria, minimum norm, perhaps, to pin down a unique solution.)

Substituting into the identity b = Az + e gives a final solution:

	b = A(A'X'XA)^(-1)A'X'(Y - Xe) + e

The choice of the matrix A and the vector e does not affect the
theoretical solution but may influence numerical stability of this
approach.  Someone else has already posted numerous references to
articles on the numerical aspects of the problem.

The problem is also fairly easy to solve using a vector of LaGrange
multipliers to handle the constraints.
--
T. Scott Thompson              email:  thompson@atlas.socsci.umn.edu
Department of Economics        phone:  (612) 625-0119
University of Minnesota        fax:    (612) 624-0209