home *** CD-ROM | disk | FTP | other *** search
- Newsgroups: sci.math.stat
- Path: sparky!uunet!spool.mu.edu!umn.edu!thompson
- From: thompson@atlas.socsci.umn.edu (T. Scott Thompson)
- Subject: Re: LS with linear constraints
- Message-ID: <thompson.722556448@kiyotaki.econ.umn.edu>
- Keywords: least squares
- Sender: news@news2.cis.umn.edu (Usenet News Administration)
- Nntp-Posting-Host: kiyotaki.econ.umn.edu
- Reply-To: thompson@atlas.socsci.umn.edu
- Organization: Economics Department, University of Minnesota
- References: <1992Nov20.182350.8925@midway.uchicago.edu>
- Distribution: usa
- Date: Mon, 23 Nov 1992 22:07:28 GMT
- Lines: 48
-
- 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
-