🚀 go-pugleaf

Some time ago I inquired about solving a problem in least squares in
which all of the unkowns are required to be positive.  Some people
requested that a summary of the replies be posted or sent to them.
(Sorry I took so long to compile this.) So here is a summary:

------------ Original problem statement --------------------

I have what effectively amounts to a linear regression problem with
contraints.  I have observations, (X_i, Y_i), where X_i = (X_i1, ...,
X_ij), and I am trying to fit the model,  Y_i = sum_j a_j X_ij + e_i.
The catch is that I must have all of the a_j >= 0. 

Is this a common problem?  Is there some standard solution to it?
Does anyone have any ideas how to solve it?

------------ Maximum Likelihood and Logarithms --------------

Several people suggested that I let b_j = log(a_j).  That way, a_j
would be guaranteed to remain positive as b_j is allowed to range from
-infty to +infty.  One could either make the substitution directly,
ie., substitute exp(b_j) for a_j in the above formulation, or use MLE
to derive a solution.  In either case, the problem appears to be
nonlinear.

----------- Use squared coefficients ------------------------

A couple people suggested the use of squared coefficients.  In this
case, the substitution would be b_j^2 in place of a_j in the above
formulation.  This is a nonlinear method.

----------- Use all possible subsets ------------------------

One person suggested that the regression program be run on all
possible subsets and that the solution be chosen with the minimum sum
of squared errors and all coefficients positive:

  y on x1 x2 x3
  y on x1 x2
       x1    x3
          x2 x3
       x1
          x2
             x3

This is linear in each subset of coefficients but is combinatorial in
the number of coefficients.  It is probably a good method if the
number of independent variables is small.

----------- Non-negative least squares -----------------------

One person informed me that "the problem you ask about is called the
non-negative least squares problem."  After some research, I
discovered that it is also called least squares with inequality
constraints and is a subset of the domain of nonlinear programming.
This appears to be the best way to solve the problem for any
nontrivial number of unknowns and because I sometimes have up to 100
unknowns, this is the method that I have chosen to use.  The person
that clued me in also sent me come C code which works great.

Here is a reference that I received (from another person) on the
subject:

  Bremner, J.M. (1982)  An algorithm for nonnegative least squares and
    projection onto cones.  Compstat 1982, Part I: Proceedings in
    Computational Statistics.  Vienna: Physica-Verlag.

----------- Fuzzy Kriging -------------------------------------

I also received the following (for anyone really interested in the
subject): 

well, instead of just the usual normal equations, one has to introduce
lagrange multipliers and use the kuhn-tucker conditions to get
analogues of the normal equations. see for example any book on
constrained optimization, or for the derivation of a generalized
estimator, my paper "fuzzy kriging", fuzzy sets and systems, 33(1989),
315--332.  (phil diamond)

----------- The End -------------------------------------------

Darrell