active set algorithm

solve linear least squares problem with nonnegative variables

Description

This function solves linear least squares problem with nonnegative variables using the active set algorithm described in:
Portugal, Judice and Vicente, A comparison of block pivoting and interior point algorithms for linear least squares problems with nonnegative variables, Mathematics of Computation, 63(1994), pp. 625-643

Acknowledgements

This file inspired Lbfgsb (L Bfgs B) Mex Wrapper.

• MATLAB release: MATLAB 7.1.0 (R14SP3)

[Greg Reynolds]

I experienced the same bug as the first comment.

[Christos B.]

No comments.....

>> activeset(rand(13,3),rand(13,1))
??? Attempted to access r(1); index out of bounds because numel(r)=0.

Error in ==> activeset at 32
r = r(1);

>> activeset(rand(13,3),rand(13,1))
??? Attempted to access r(1); index out of bounds because numel(r)=0.

Error in ==> activeset at 32
r = r(1);

>> activeset(rand(13,3),rand(13,1))
??? Attempted to access r(1); index out of bounds because numel(r)=0.

Error in ==> activeset at 32
r = r(1);

>> activeset(rand(13,3),rand(13,1))
??? Attempted to access r(1); index out of bounds because numel(r)=0.

Error in ==> activeset at 32
r = r(1);

>> activeset(rand(13,3),rand(13,1))

ans =

0
0.5812
0.3521

>>

[John D'Errico]

A few quick tests. The numbers can speak for themselves.

m=50;m=2*n;A=rand(n,m);b=rand(n,1);
tic,[x,y] = activeset(A,b);toc
Elapsed time is 0.089039 seconds.

tic,x0 = lsqnonneg(A,b);toc
Elapsed time is 1.265998 seconds.

std(x-x0)
ans =
2.5407e-16

m=10;n=20*m;A=rand(n,m);b=rand(n,1);
tic,[x,y] = activeset(A,b);toc
Elapsed time is 0.017188 seconds.

tic,x0 = lsqnonneg(A,b);toc
Elapsed time is 0.020343 seconds.

m=200;n=m;A=rand(n,m);b=rand(n,1);
tic,x0 = lsqnonneg(A,b);toc
Elapsed time is 10.426879 seconds.

tic,[x,y] = activeset(A,b);toc
Elapsed time is 0.245311 seconds.

What else is there to say? The help is reasonable, though not expansive. Lsqnonneg returns a bit more in terms of secondary information.

Did I forget to tell you to look at the times? Well done.