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. > A solution is given in Kennedy and Gentle, the solution is
  22.  
  23. >  b = (X'X + C'C)^{-1} X'Y.
  24.  
  25. > Can anyone show me other methods/solutions to this constrained
  26. > LS problem?  Thanks in advance.
  27.  
  28. If you look in Kennedy and Gentle again you will see that this
  29. "solution" is in fact a solution only for the case where d = 0.
  30.  
  31. One intuitive solution to the general problem can be obtained by
  32. noting that Cb = d if and only if b = Az + e for some z in R^(p-q),
  33. where A is any px(p-q) matrix of rank p-q for which CA = 0, and e is
  34. any particular solution to the equation Ce = d.  So the constrained
  35. problem is equivalent to the unconstrained problem:
  36.  
  37.     min (Y - Xe - XAz)'(Y - Xe - XAz)
  38.      z
  39.  
  40. which has solution
  41.  
  42.     z = (A'X'XA)^(-1)A'X'(Y - Xe)
  43.  
  44. assuming that the inverse exists.  (If not, then there is no unique
  45. solution to the original problem, and you need some additional
  46. criteria, minimum norm, perhaps, to pin down a unique solution.)
  47.  
  48. Substituting into the identity b = Az + e gives a final solution:
  49.  
  50.     b = A(A'X'XA)^(-1)A'X'(Y - Xe) + e
  51.  
  52. The choice of the matrix A and the vector e does not affect the
  53. theoretical solution but may influence numerical stability of this
  54. approach.  Someone else has already posted numerous references to
  55. articles on the numerical aspects of the problem.
  56.  
  57. The problem is also fairly easy to solve using a vector of LaGrange
  58. multipliers to handle the constraints.
  59. --
  60. T. Scott Thompson              email:  thompson@atlas.socsci.umn.edu
  61. Department of Economics        phone:  (612) 625-0119
  62. University of Minnesota        fax:    (612) 624-0209
  63.