NNLS

> Hi!
> In a least squares fitting application, I'm trying to determine the parameters x_1, x_2
> and x_3 so that the function
> f(x_1, x_2, x_3) = \sum_{i=1}^N (a_i*x_1 + b_i*x_2 + c_i*x_3 - d_i)^2
> is minimized under the constrains x_1, x_2, x_3 >= 0 (LaTeX notation)
> I was pointed to the keyword "nonnegative least squares" (NNLS), but wasn't able to
> find out much about this: Lawson, Hanson: "Solving Least Squares Problems", Ch. 23
> Briggs: "High Fidelity Deconvolution of Moderately Resolved Sources", Ch. 4.3
> Can you recommend further literature or web resources on this topic, ideally with examples
> on how to solve this type of problem?

Any NLP solver can solve these type of problems quite efficiently. See e.g.
http://www.princeton.edu/~rvdb/ampl/nlmodels/nnls/index.html
A GAMS version can look like:

   1  set
   2    i /1*1000/
   3    j /1*300/
   4  ;
   5   
   6  parameters
   7     b(i)
   8     A(i,j)
   9  ;
  10   
  11  a(i,j)$(uniform(0,1) < 0.21) = 10*(uniform(0,1)-1);
  12  parameter x0(j);
  13  x0(j) = uniform(0,1);
  14  b(i) = sum(j, a(i,j)*x0(j)) + 100*(uniform(0,1)-0.5)
  15   
  16  positive variable x(j);
  17  variable sum_sqs;
  18   
  19  equation esum_sqs;
  20   
  21  esum_sqs.. sum_sqs =e= sum(i, sqr[ b(i) - sum(j, A(i,j)*x[j]) ]);
  22   
  23  model m /all/;
  24  solve m minimizing sum_sqs using nlp;
  25   
  26   
  27  *conopt : 0.702 seconds
  28  *minos :  1.264
  29  *snopt :  0.343
  30  *knitro : 7.385
  31  *ipopt :  1.088