nnls {lsei}

Least Squares and Quadratic Programming under Nonnegativity Constraints

Description

These functions are particularly useful for solving least squares or quadratic programming problems when some or all of the solution values are subject to nonnegativity constraint. One may further restrict the NN-restricted coefficients to have a fixed positive sum.

Usage

nnls(a, b) 
pnnls(a, b, k=0, sum=NULL) 
pnnqp(q, p, k=0, sum=NULL, tol=1e-20)

Arguments

a

Design matrix.

b

Response vector.

k

Integer, meaning that the first k coefficients are not NN-restricted.

sum

= NULL, if NN-restricted coefficients are not further restricted to have a fixed sum;

= a positive value, if NN-restricted coefficients are further restricted to have a fixed positive sum.

q

Positive semidefinite matrix of numeric values for the quadratic term of a quadratic programming problem.

p

Vector of numeric values for the linear term of a quadratic programming problem.

tol

Tolerance used for calculating pseudo-rank of q.

Details

Function nnls solves the least squares problem under nonnegativity (NN) constraints. It is an R interface to the NNLS function that is described in Lawson and Hanson (1974, 1995). Its Fortran implementation is public domain and available at http://www.netlib.org/lawson-hanson/ (with slight modifications by Yong Wang for compatibility with the lastest Fortran compiler.)

Given matrix a and vector b, nnls solves the nonnegativity least squares problem:

\mathrm{minimize \ \ } || a x - b ||,

\mathrm{\ \ \ subject\ to\ \ } x \ge 0.

Function pnnls also solves the above nonnegativity least squares problem when k=0, but it may also leave the first k coefficients unrestricted. The output value of k can be smaller than the input one, if a has linearly dependent columns. If sum is a positive value, pnnls solves the problem by further restricting that the NN-restricted coefficients must sum to the given value.

Function pnnqp solves the quadratic programming problem

\mathrm{minimize\ \ } \frac12 x^T q x + p^T x,

when only some or all coefficients are restricted by nonnegativity. The quadratic programming problem is solved by transforming the problem into a least squares one under the same constraints, which is then solved by function pnnls. Arguments k and sum have the same meanings as for pnnls.

Functions nnls, pnnls and pnnqp are able to return any zero-valued solution as 0 exactly. This differs from functions lsei and qp, which may produce very small values for exactly 0s, thanks to numerical errors.

Value

x

Solution

r

The upper-triangular matrix Q*a, pivoted by variables in the order of index, when sum=NULL. If sum > 0, r is for the transformed a.

b

The vector Q*b, pivoted by variables in the order of index, when sum=NULL. If sum > 0, b is for the transformed b.

index

Indices of the columns of r; those unrestricted and in the positive set are first given, and then those in the zero set.

rnorm

Euclidean norm of the residual vector.

mode

= 1, successful computation;

= 2, bad dimensions of the problem;

= 3, iteration count exceeded (more than 3 times the number of variables iterations).

k

Number of the first few coefficients that are truly not NN-restricted.

Author(s)

Yong Wang <[e-mail]>

References

Lawson and Hanson (1974, 1995). Solving Least Squares Problems. Englewood Cliffs, N.J., Prentice-Hall.

Dax (1990). The smallest point of a polytope. Journal of Optimization Theory and Applications, 64, pp. 429-432.

Wang (2010). Fisher scoring: An interpolation family and its Monte Carlo implementations. Computational Statistics and Data Analysis, 54, pp. 1744-1755.

See Also

lsei, hfti.

Examples

a = matrix(rnorm(40), nrow=10)
b = drop(a %*% c(0,1,-1,1)) + rnorm(10)
nnls(a, b)$x                     # constraint x >= 0
pnnls(a, b, k=0)$x               # same as nnls(a, b)
pnnls(a, b, k=2)$x               # first two coeffs are not NN-constrained
pnnls(a, b, k=2, sum=1)$x        # NN-constrained coeffs must sum to 1
pnnls(a, b, k=2, sum=2)$x        # NN-constrained coeffs must sum to 2
q = crossprod(a)
p = -drop(crossprod(b, a))
pnnqp(q, p, k=2, sum=2)$x        # same solution

pnnls(a, b, sum=1)$x             # zeros found exactly
pnnqp(q, p, sum=1)$x             # zeros found exactly
lsei(a, b, rep(1,4), 1, lower=0) # zeros not so exact