home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / stat / 2411 < prev    next >
Encoding:
Text File  |  1992-11-23  |  2.3 KB  |  64 lines
  1. Newsgroups: sci.math.stat
  2. Path: sparky!uunet!spool.mu.edu!umn.edu!thompson
  3. From: thompson@atlas.socsci.umn.edu (T. Scott Thompson)
  4. Subject: Re: LS with linear constraints
  5. Message-ID: <thompson.722556448@kiyotaki.econ.umn.edu>
  6. Keywords: least squares
  7. Sender: news@news2.cis.umn.edu (Usenet News Administration)
  8. Nntp-Posting-Host: kiyotaki.econ.umn.edu
  9. Reply-To: thompson@atlas.socsci.umn.edu
  10. Organization: Economics Department, University of Minnesota
  11. References: <1992Nov20.182350.8925@midway.uchicago.edu>
  12. Distribution: usa
  13. Date: Mon, 23 Nov 1992 22:07:28 GMT
  14. Lines: 48
  15.  
  16. ngo1@quads.uchicago.edu (hang-yue  ngo) writes:
  17.  
  18. >I have a problem:  minimize (Y - Xb)'(Y - Xb) with respect to b
  19. > subject to Cb = d.  b  is a px1 vector and C is a qxp matrix.
  20. > The matrix X may not be full rank (i.e., rank(X) = r < p).
  21. > 
  22. > A solution is given in Kennedy and Gentle, the solution is
  23.  
  24. >  b = (X'X + C'C)^{-1} X'Y.
  25.  
  26. > Can anyone show me other methods/solutions to this constrained
  27. > LS problem?  Thanks in advance.
  28.  
  29. If you look in Kennedy and Gentle again you will see that this
  30. "solution" is in fact a solution only for the case where d = 0.
  31.  
  32. One intuitive solution to the general problem can be obtained by
  33. noting that Cb = d if and only if b = Az + e for some z in R^(p-q),
  34. where A is any px(p-q) matrix of rank p-q for which CA = 0, and e is
  35. any particular solution to the equation Ce = d.  So the constrained
  36. problem is equivalent to the unconstrained problem:
  37.  
  38.     min (Y - Xe - XAz)'(Y - Xe - XAz)
  39.      z
  40.  
  41. which has solution
  42.  
  43.     z = (A'X'XA)^(-1)A'X'(Y - Xe)
  44.  
  45. assuming that the inverse exists.  (If not, then there is no unique
  46. solution to the original problem, and you need some additional
  47. criteria, minimum norm, perhaps, to pin down a unique solution.)
  48.  
  49. Substituting into the identity b = Az + e gives a final solution:
  50.  
  51.     b = A(A'X'XA)^(-1)A'X'(Y - Xe) + e
  52.  
  53. The choice of the matrix A and the vector e does not affect the
  54. theoretical solution but may influence numerical stability of this
  55. approach.  Someone else has already posted numerous references to
  56. articles on the numerical aspects of the problem.
  57.  
  58. The problem is also fairly easy to solve using a vector of LaGrange
  59. multipliers to handle the constraints.
  60. --
  61. T. Scott Thompson              email:  thompson@atlas.socsci.umn.edu
  62. Department of Economics        phone:  (612) 625-0119
  63. University of Minnesota        fax:    (612) 624-0209
  64.