home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / stat / 1485 < prev    next >
Encoding:
Internet Message Format  |  1992-07-21  |  3.8 KB
  1. Path: sparky!uunet!cs.utexas.edu!usc!wupost!m.cs.uiuc.edu!roundup.crhc.uiuc.edu!uirvli!hougen
  2. From: hougen@uirvli.csl.uiuc.edu (Darrell Roy Hougen)
  3. Newsgroups: sci.math.stat
  4. Subject: Summary: Least Squares with Constraints
  5. Date: 22 Jul 1992 01:28:27 GMT
  6. Organization: Center for Reliable and High-Performance Computing, University of Illinois at Urbana-Champaign
  7. Lines: 83
  8. Message-ID: <l6pedrINN4b6@roundup.crhc.uiuc.edu>
  9. NNTP-Posting-Host: uirvli.csl.uiuc.edu
  10. Summary: Summary: Least Squares with Constraints
  11. Keywords: Least Squares, Constraints
  12.  
  13.  
  14. Some time ago I inquired about solving a problem in least squares in
  15. which all of the unkowns are required to be positive.  Some people
  16. requested that a summary of the replies be posted or sent to them.
  17. (Sorry I took so long to compile this.) So here is a summary:
  18.  
  19. ------------ Original problem statement --------------------
  20.  
  21. I have what effectively amounts to a linear regression problem with
  22. contraints.  I have observations, (X_i, Y_i), where X_i = (X_i1, ...,
  23. X_ij), and I am trying to fit the model,  Y_i = sum_j a_j X_ij + e_i.
  24. The catch is that I must have all of the a_j >= 0. 
  25.  
  26. Is this a common problem?  Is there some standard solution to it?
  27. Does anyone have any ideas how to solve it?
  28.  
  29. ------------ Maximum Likelihood and Logarithms --------------
  30.  
  31. Several people suggested that I let b_j = log(a_j).  That way, a_j
  32. would be guaranteed to remain positive as b_j is allowed to range from
  33. -infty to +infty.  One could either make the substitution directly,
  34. ie., substitute exp(b_j) for a_j in the above formulation, or use MLE
  35. to derive a solution.  In either case, the problem appears to be
  36. nonlinear.
  37.  
  38. ----------- Use squared coefficients ------------------------
  39.  
  40. A couple people suggested the use of squared coefficients.  In this
  41. case, the substitution would be b_j^2 in place of a_j in the above
  42. formulation.  This is a nonlinear method.
  43.  
  44. ----------- Use all possible subsets ------------------------
  45.  
  46. One person suggested that the regression program be run on all
  47. possible subsets and that the solution be chosen with the minimum sum
  48. of squared errors and all coefficients positive:
  49.  
  50.   y on x1 x2 x3
  51.   y on x1 x2
  52.        x1    x3
  53.           x2 x3
  54.        x1
  55.           x2
  56.              x3
  57.  
  58. This is linear in each subset of coefficients but is combinatorial in
  59. the number of coefficients.  It is probably a good method if the
  60. number of independent variables is small.
  61.  
  62. ----------- Non-negative least squares -----------------------
  63.  
  64. One person informed me that "the problem you ask about is called the
  65. non-negative least squares problem."  After some research, I
  66. discovered that it is also called least squares with inequality
  67. constraints and is a subset of the domain of nonlinear programming.
  68. This appears to be the best way to solve the problem for any
  69. nontrivial number of unknowns and because I sometimes have up to 100
  70. unknowns, this is the method that I have chosen to use.  The person
  71. that clued me in also sent me come C code which works great.
  72.  
  73. Here is a reference that I received (from another person) on the
  74. subject:
  75.  
  76.   Bremner, J.M. (1982)  An algorithm for nonnegative least squares and
  77.     projection onto cones.  Compstat 1982, Part I: Proceedings in
  78.     Computational Statistics.  Vienna: Physica-Verlag.
  79.  
  80. ----------- Fuzzy Kriging -------------------------------------
  81.  
  82. I also received the following (for anyone really interested in the
  83. subject): 
  84.  
  85. well, instead of just the usual normal equations, one has to introduce
  86. lagrange multipliers and use the kuhn-tucker conditions to get
  87. analogues of the normal equations. see for example any book on
  88. constrained optimization, or for the derivation of a generalized
  89. estimator, my paper "fuzzy kriging", fuzzy sets and systems, 33(1989),
  90. 315--332.  (phil diamond)
  91.  
  92. ----------- The End -------------------------------------------
  93.  
  94. Darrell
  95.  
  96.