Package com.imsl.math

Class NonlinLeastSquares

java.lang.Object
com.imsl.math.NonlinLeastSquares
All Implemented Interfaces:
Serializable, Cloneable
public class NonlinLeastSquares extends Object implements Serializable, Cloneable
Nonlinear least squares.

NonlinLeastSquares is based on the MINPACK routine LMDIF by Moré et al. (1980). It uses a modified Levenberg-Marquardt method to solve nonlinear least squares problems. The problem is stated as follows:

$$\mathop {\min }\limits_{x \in R^n } \frac{1}{2}F\left( x \right)^T F\left( x \right) = \frac{1}{2}\sum\limits_{i = 1}^m {f_i } \left( x \right)^2$$

where \(m \ge n\), \(F:\,\,R^n \to R^m\), and \(f_i(x)\) is the i-th component function of F(x). From a current point, the algorithm uses the trust region approach:

$$\mathop {\min }\limits_{x_n \in R^n } \left\| {F\left( {x_c } \right) + J\left( {x_c } \right)\left( {x_n - x_c } \right)} \right\|_2$$

subject to

$$\left\| {x_n - x_c } \right\|_2 \le \delta _c$$

to get a new point \(x_n\), which is computed as

$$x_n = x_c - \left( {J\left( {x_c } \right)^T J\left( {x_c } \right) + \mu _c I} \right)^{ - 1} J\left( {x_c } \right)^T F\left( {x_c } \right)$$

where \(\mu _c = 0\) if \(\ \delta _c \ge \left\| {\left( {J\left( {x_c } \right)^T J\left( {x_c } \right)} \right)^{-1} \,\,J\left( {x_c } \right)^T F\left( {x_c } \right)} \right\|_2\) and \(\mu _c > 0\) otherwise. \(F(x_c)\) and \(J(x_c)\) are the function values and the Jacobian evaluated at the current point \(x_c\). This procedure is repeated until the stopping criteria are satisfied. The first stopping criteria occurs when the norm of the function is less than the value set in method setAbsoluteTolerance. The second stopping criteria occurs when the norm of the scaled gradient is less than the value set in method setGradientTolerance. The third stopping criteria occurs when the scaled distance between the last two steps is less than the value set by method setStepTolerance. For more details, see Levenberg (1944), Marquardt (1963), or Dennis and Schnabel (1983, Chapter 10).

A finite-difference method is used to estimate the Jacobian when the user supplied function, f, defines the least-squares problem. Whenever the exact Jacobian can be easily provided, f should implement NonlinLeastSquares.Jacobian.

See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static interface 
    NonlinLeastSquares.Function
    Public interface for the user supplied function to the NonlinLeastSquares object.
    static interface 
    NonlinLeastSquares.Jacobian
    Public interface for the user supplied function to the NonlinLeastSquares object.
    static class 
    NonlinLeastSquares.TooManyIterationsException
    Too many iterations.

  • Constructor Summary

    Constructors
    Constructor
    Description
    NonlinLeastSquares(int m, int n)
    Creates an object to solve a nonlinear least squares problem.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    getErrorStatus()
    Get information about the performance of NonlinLeastSquares.
    int
    getNumberOfThreads()
    Returns the number of java.lang.Thread instances used for parallel processing.
    void
    setAbsoluteTolerance(double absoluteTolerance)
    Set the absolute function tolerance.
    void
    setDigits(int ngood)
    Set the number of good digits in the function.
    void
    setFalseConvergenceTolerance(double falseConvergenceTolerance)
    Set the false convergence tolerance.
    void
    setFscale(double[] fscale)
    Set the diagonal scaling matrix for the functions.
    void
    setGradientTolerance(double gradientTolerance)
    Set the scaled gradient tolerance stopping critierion.
    void
    setGuess(double[] xguess)
    Set the initial guess of the minimum point of the input function.
    void
    setInitialTrustRegion(double initialTrustRegion)
    Set the initial trust region radius.
    void
    setMaximumStepsize(double maximumStepsize)
    Set the maximum allowable stepsize to use.
    void
    setMaxIterations(int maxIterations)
    Set the maximum number of iterations allowed.
    void
    setNumberOfThreads(int numberOfThreads)
    Sets the number of java.lang.Thread instances to be used for parallel processing.
    void
    setRelativeTolerance(double relativeTolerance)
    Set the relative function tolerance.
    void
    setStepTolerance(double stepTolerance)
    Set the scaled step tolerance.
    void
    setXscale(double[] xscale)
    Set the diagonal scaling matrix for the variables.
    double[]
    solve(NonlinLeastSquares.Function F)
    Solve a nonlinear least-squares problem using a modified Levenberg-Marquardt algorithm and a Jacobian.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • NonlinLeastSquares

      public NonlinLeastSquares(int m, int n)
      Creates an object to solve a nonlinear least squares problem.
      Parameters:
      m - is the number of functions
      n - is the number of variables. n must be less than or equal to m.

  • Method Details

    • setNumberOfThreads

      public void setNumberOfThreads(int numberOfThreads)
      Sets the number of java.lang.Thread instances to be used for parallel processing.
      Parameters:
      numberOfThreads - an int specifying the number of java.lang.Thread instances to be used for parallel processing. If numberOfThreads is greater than 1, then interface Function.f is evaluated in parallel and Function.f must be thread-safe. Otherwise, unexpected behavior can occur.

      Default: numberOfThreads = 1.

    • getNumberOfThreads

      public int getNumberOfThreads()
      Returns the number of java.lang.Thread instances used for parallel processing.
      Returns:
      an int containing the number of java.lang.Thread instances used for parallel processing.

    • solve

      public double[] solve(NonlinLeastSquares.Function F) throws NonlinLeastSquares.TooManyIterationsException
      Solve a nonlinear least-squares problem using a modified Levenberg-Marquardt algorithm and a Jacobian.
      Parameters:
      F - User supplied function that defines the least-squares problem. If F implements Jacobian then its Jacobian is used. Otherwise, a finite difference Jacobian is used.
      Returns:
      a double array of length n containing the approximate solution
      Throws:
      NonlinLeastSquares.TooManyIterationsException - is thrown if the number of iterations exceeds MaxIterations. MaxIterations is set to 100 by default.

    • setGuess

      public void setGuess(double[] xguess)
      Set the initial guess of the minimum point of the input function. If this member function is not called, an initial guess of 0.0 is used.
      Parameters:
      xguess - a double array specifying the initial guess of the minimum point of the input function

    • setXscale

      public void setXscale(double[] xscale)
      Set the diagonal scaling matrix for the variables.
      Parameters:
      xscale - a double array specifying the diagonal scaling matrix for the variables. xscale is used in scaling the gradient and the distance between two points. See methods setGradientTolerance and setStepTolerance for more detail. By default, the identity is used.
      Throws:
      IllegalArgumentException - is thrown if any of the elements of xscale is less than or equal to 0

    • setFscale

      public void setFscale(double[] fscale)
      Set the diagonal scaling matrix for the functions.
      Parameters:
      fscale - a double array specifying the diagonal scaling matrix for the functions. The i-th component of fscale is a positive scalar specifying the reciprocal magnitude of the i-th component function of the problem. By default, the identity is used.
      Throws:
      IllegalArgumentException - is thrown if any of the elements of fscale is less than or equal to 0

    • setMaximumStepsize

      public void setMaximumStepsize(double maximumStepsize)
      Set the maximum allowable stepsize to use. If this member function is not called, maximum stepsize is set to a default value based on a scaled xguess.
      Parameters:
      maximumStepsize - a nonnegative double value specifying the maximum allowable stepsize.
      Throws:
      IllegalArgumentException - is thrown if maximumStepsize is less than or equal to 0

    • setDigits

      public void setDigits(int ngood)
      Set the number of good digits in the function. If this member function is not called, the number of good digits is set to 7.
      Parameters:
      ngood - an int specifying the number of good digits in the user supplied function which defines the least-squares problem
      Throws:
      IllegalArgumentException - is thrown if ngood is less than or equal to 0

    • setMaxIterations

      public void setMaxIterations(int maxIterations)
      Set the maximum number of iterations allowed. If this member function is not called, the maximum number of iterations is set to 100.
      Parameters:
      maxIterations - an int specifying the maximum number of iterations allowed
      Throws:
      IllegalArgumentException - is thrown if maxIterations is less than or equal to 0

    • setGradientTolerance

      public void setGradientTolerance(double gradientTolerance)
      Set the scaled gradient tolerance stopping critierion.
      Parameters:
      gradientTolerance - a double specifying the scaled gradient tolerance used in stopping criteria. The i-th component of the scaled gradient at x is calculated as $$ \frac{|{g_i}| * \max(|x_i|,\, \frac{1}{s_i} )}{\frac{1}{2} ||F(x)||_2^2 } $$ where $$g_i = \left ( J(x)^TF(x) \right )_i * (f_s)^2_i \,\,\mbox{,}$$ J(x) is the Jacobian, s = xscale, \(f_s\)= fscale, and $$ ||F(x)||_2^2 = \sum_{i=1}^m f_i(x)^2 \,\mbox{.} $$ When the norm of the scaled gradient is less than gradientTolerance the procedure stops.

      By default, gradientTolerance = \(\sqrt[3]{\varepsilon }\) where \(\varepsilon\) is machine precision.

      Throws:
      IllegalArgumentException - is thrown if gradientTolerance is less than or equal to 0

    • setStepTolerance

      public void setStepTolerance(double stepTolerance)
      Set the scaled step tolerance.
      Parameters:
      stepTolerance - a double scalar value specifying the scaled step tolerance used in stopping criteria. The i-th component of the scaled step between two points x and y is computed as $$ \frac{| x_i - y_i |}{\max(|x_i|, \frac{1}{s_i})} $$ where s = xscale. When the scaled distance between the last two steps is less than stepTolerance the procedure stops.

      By default, stepTolerance = \(\sqrt[3]{\varepsilon }\) where \(\varepsilon\) is machine precision.

      Throws:
      IllegalArgumentException - is thrown if stepTolerance is less than or equal to 0

    • setRelativeTolerance

      public void setRelativeTolerance(double relativeTolerance)
      Set the relative function tolerance.
      Parameters:
      relativeTolerance - a double scalar value specifying the relative function tolerance

      Default: relativeTolerance = 1.0e-20

      Throws:
      IllegalArgumentException - is thrown if relativeTolerance is less than or equal to 0

    • setAbsoluteTolerance

      public void setAbsoluteTolerance(double absoluteTolerance)
      Set the absolute function tolerance.
      Parameters:
      absoluteTolerance - a double scalar value specifying the absolute function tolerance. When the norm of the function is less than absoluteTolerance the procedure stops.

      Default: absoluteTolerance = 1.0e-32

      Throws:
      IllegalArgumentException - is thrown if absoluteTolerance is less than or equal to 0

    • setFalseConvergenceTolerance

      public void setFalseConvergenceTolerance(double falseConvergenceTolerance)
      Set the false convergence tolerance. If this member function is not called, 100.0e-16 is used as the false convergence tolerance.
      Parameters:
      falseConvergenceTolerance - a double scalar value specifying the false convergence tolerance
      Throws:
      IllegalArgumentException - is thrown if falseConvergenceTolerance is less than or equal to 0

    • setInitialTrustRegion

      public void setInitialTrustRegion(double initialTrustRegion)
      Set the initial trust region radius. If this member function is not called, a default is set based on the initial scaled Cauchy step.
      Parameters:
      initialTrustRegion - a double scalar value specifying the initial trust region radius
      Throws:
      IllegalArgumentException - is thrown if initialTrustRegion is less than or equal to 0

    • getErrorStatus

      public int getErrorStatus()
      Get information about the performance of NonlinLeastSquares.
      Returns:
      an int specifying information about convergence.
      VALUEDESCRIPTION
      0All convergence tests were met.
      1Scaled step tolerance was satisfied. The current point may be an approximate local solution, or the algorithm is making very slow progress and is not near a solution, or StepTolerance is too big.
      2Scaled actual and predicted reductions in the function are less than or equal to the relative function convergence tolerance RelativeTolerance.
      3Iterates appear to be converging to a noncritical point. Incorrect gradient information, a discontinuous function, or stopping tolerances being too tight may be the cause.
      4Five consecutive steps with the maximum stepsize have been taken. Either the function is unbounded below, or has a finite asymptote in some direction, or the maximum stepsize is too small.

      See Also: