nnls: Least Squares and Quadratic Programming under Nonnegativity Constraints

Description

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.

pnnls solves the least squares problem when only part of the coefficients are subject to nonnegativity constraints. It also allows the NN-restricted coefficients to be further restricted to have a fixed positive sum.

pnnqp solves the quadratic programming problem when solution values are partly subject to nonnegativity constraints. It also allows the NN-restricted coefficients to be further restricted to have a fixed positive sum.

These functions are particularly useful for finding zeros exactly.

Usage

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

Arguments

Design matrix.

Response vector.

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.

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

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

tol

Tolerance used for calculating pseudo-rank of q.

Value

Solution

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.

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).

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

Details

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 different from the input, 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.

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.

Examples

Run this code

# NOT RUN {
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
# }

Run the code above in your browser using DataCamp Workspace