nnls

0th

Percentile

Least Squares and Quadratic Programming under Nonnegativity Constraints

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.

Keywords
array , algebra
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

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.

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.

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.

Aliases
  • nnls
  • pnnls
  • pnnqp
Examples
# 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
# }
Documentation reproduced from package lsei, version 1.2-0, License: GPL (>= 2)

Community examples

Looks like there are no examples yet.