com.imsl.math

Class NonNegativeLeastSquares

java.lang.Object

com.imsl.math.NonNegativeLeastSquares

All Implemented Interfaces:

Serializable, Cloneable

public class NonNegativeLeastSquares
extends Object
implements Serializable, Cloneable

Solves a linear least squares problem with nonnegativity constraints. NonNegativeLeastSquares solves the problem $$\min_x\|Ax-b\|^2$$ subject to the condition \(x \ge 0\).

If a starting point \(x_0\) is provided, those entries of \(x_0\) that are \(\gt0\) are first combined with a descent gradient component. The start point is the origin. When \(x_0\) is not provided the algorithm uses only the gradient to verify that an optimum has been found. The algorithm completes using only the gradient components to reach an optimum. For more information, see Lawson and Hanson (1974).

See Also:

BoundedVariableLeastSquares, Example, Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	NonNegativeLeastSquares.TooManyIterException Maximum number of iterations has been exceeded.
static class	NonNegativeLeastSquares.TooMuchTimeException Maximum time allowed for solve is exceeded.

Constructor Summary

Constructors

Constructor and Description
NonNegativeLeastSquares(double[][] a, double[] b) Construct a new NonNegativeLeastSquares instance to solve Ax-b where x is a vector of n unknowns.

Method Summary

Modifier and Type	Method and Description
double[]	getDualSolution() Returns the dual solution vector, w.
int	getIterations() Returns the number of iterations used to find the solution.
double	getResidualNorm() Returns the euclidean norm of the residual vector, \(\|Ax-b\|^2\).
double[]	getSolution() Returns the solution to the problem, x.
void	setDualTolerance(double dualTolerance) Sets the dual tolerance.
void	setGuess(double[] guess) Sets the initial guess.
void	setMaximumTime(long maximumTime) Sets the maximum time allowed for the solve step.
void	setMaxIterations(int maxIterations) Sets the maximum number of iterations.
void	setNormTolerance(double normTolerance) Sets the residual norm tolerance.
void	setRankTolerance(double rankTolerance) Sets the tolerance used for the incoming column rank deficient check.
void	solve() Finds the solution to the problem for the current constraints.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

NonNegativeLeastSquares

public NonNegativeLeastSquares(double[][] a,
                               double[] b)

Construct a new NonNegativeLeastSquares instance to solve Ax-b where x is a vector of n unknowns.

Parameters:

a - the double input matrix.

b - a double array of length a.length.

Method Detail

setMaxIterations

public void setMaxIterations(int maxIterations)

Sets the maximum number of iterations.

Parameters:

maxIterations - an int specifying the maximum number of iterations. The default is three times a[0].length.

setGuess

public void setGuess(double[] guess)

Sets the initial guess.

Parameters:

guess - a double array containing the initial guess. If set, the guess is used in a two-phase algorithm where the positive components are matched with positive gradients to choose an incoming column. If not set, the algorithm uses only the gradient to verify that an optimum has been found.

setMaximumTime

public void setMaximumTime(long maximumTime)

Sets the maximum time allowed for the solve step.

Parameters:

maximumTime - a long value specifying the maximum time, in milliseconds, to be allowed for the solve step. If maximumTime is less than or equal to zero, then no time limit is imposed. By default, there is no time limit.

setRankTolerance

public void setRankTolerance(double rankTolerance)

Sets the tolerance used for the incoming column rank deficient check.

Parameters:

rankTolerance - a double value used to check for rank deficiency. The default value is 2.220e-016.

setDualTolerance

public void setDualTolerance(double dualTolerance)

Sets the dual tolerance. The computation stops if largest gradient is smaller than this. The default value is 0.

Parameters:

dualTolerance - a double containing the dual tolerance.

setNormTolerance

public void setNormTolerance(double normTolerance)

Sets the residual norm tolerance.

Parameters:

normTolerance - a double containing the residual norm tolerance. The computation stops if \( {||\mbox{rnorm}||}^2 \le{\mbox{normTolerance} \times{||b||}}\), where rnorm is the residual norm. By default, the value is 0.

solve

public void solve()
           throws NonNegativeLeastSquares.TooManyIterException,
                  NonNegativeLeastSquares.TooMuchTimeException

Finds the solution to the problem for the current constraints.

Throws:

TooManyIterationsException - is thrown if the maximum number of iterations is exceeded.

NonNegativeLeastSquares.TooMuchTimeException - is thrown if the maximum time allowed for solve is exceeded.

NonNegativeLeastSquares.TooManyIterException

getResidualNorm

public double getResidualNorm()

Returns the euclidean norm of the residual vector, \(\|Ax-b\|^2\).

Returns:

a double containing the euclidean norm of the residual vector.

getIterations

public int getIterations()

Returns the number of iterations used to find the solution.

Returns:

an int containing the number of iterations.

getSolution

public double[] getSolution()

Returns the solution to the problem, x.

Returns:

a double array containing the solution.

getDualSolution

public double[] getDualSolution()

Returns the dual solution vector, w. If \(x_j = 0\) then \(w_j \le 0\), otherwise \(w_j = 0\).

Returns:

a double array containing the dual solution vector, w.