Class LMA

java.lang.Object
org.bzdev.math.LMA

public class LMA extends Object
Class to implement the Levenberg-Marquardt algorithm for solving non-linear least squares problems. A description of this algorithm can be found on the Levenberg-Marquardt Algorithm Wikipedia page and Methods for Non-Linear Least Squares Problems.

This class consists of static methods. For all the public methods, the first argument is an instance of RealValuedFunctionVA, and the last arguments are a variable-length argument list of type double[]). If a mode is provided, it will always be the second argument. There are ways variable-length arguments are handled:

  • for the sum-of-squares methods, the final argument contains parameters. These become the last arguments passed to the real-valued function. The other arguments in the variable-argument list are arrays of length n, and the ith elements of these arrays are used in computing the ith term in the sum. The order of the subset of these elements that are passed to the function is the same as the order of their arrays. Depending on a mode the first one or two arguments may be used separately and not passed to the function.
  • for the methods that find a minimum sum of squares, the last arguments are arrays of the same length, and the parameters are obtained from a separate argument. The ith elements of these arrays are used in computing the ith term in the sum. The order of the subset of these elements that are passed to the function is the same as the order of their arrays. Depending on a mode the first one or two arguments may be used separately and not passed to the function.

The methods can use one of three modes:

  • LMA.Mode.NORMAL (the default) computes the sum of the squares of values computed by the real-valued function provided as the method's first argument.
  • LMA.Mode.LEAST_SQUARES computes the sum of the squares of the terms args[0][i]-f.valueAt(args[1][i],args[2][i],...parameter[0],...) where i is the array index for the term.
  • LMA.Mode.WEIGHTED_LEAST_SQUARES computes the sum of the squares of of the terms (args[0][i]-f.valueAt(args[2][i],...,parameter[0],...))/args[1][i]
the real-valued functions must be created so as to use a fixed number of arguments. The NORMAL mode is intended for general use, whereas the other two modes are convenient for least-squares fits, with the advantage of using functions that need fewer arguments (e.g., there are a smaller number of partial derivatives to implement).
  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static class 
    LMA exception class for the case where convergence fails.
    static enum 
    The mode determining how a sum of squares is calculated.
  • Constructor Summary

    Constructors
    Constructor
    Description
    LMA()
     
  • Method Summary

    Modifier and Type
    Method
    Description
    static double
    findMin(RealValuedFunctionVA rf, double[] guess, double lambda, double nu, double limit, int iterationLimit, double[]... args)
    Find parameters that minimize the sum of squares of a real-valued function with multiple arguments.
    static double
    findMin(RealValuedFunctionVA rf, LMA.Mode mode, double[] guess, double lambda, double nu, double limit, int iterationLimit, double[]... args)
    Find parameters that minimize the sum of squares of a real-valued function with multiple arguments, specifying a mode.
    static double
    sumSquares(RealValuedFunctionVA rf, double[]... args)
    Compute the sum of the squares of a real-valued function giving various arguments.
    static double
    sumSquares(RealValuedFunctionVA rf, LMA.Mode mode, double[]... args)
    Compute the sum of the squares of a real-valued function giving various arguments, treating some arguments specially.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • LMA

      public LMA()
  • Method Details

    • sumSquares

      public static double sumSquares(RealValuedFunctionVA rf, double[]... args)
      Compute the sum of the squares of a real-valued function giving various arguments. The arguments appear first in the function calls, followed by the parameters. For the ith term in the sum, the parameters are always the same while the arguments, which vary with an index i, are given by args[0][i], args[1][i], etc., with the last args array representing the parameters. The values summed are the squares of each term.

      For example, if parameters is an array of length 3, and arg1 and arg2 are arrays of length n, then the sumSquares(rf, arg1, arg2, parameters) will call rf.valueAt(arg1[i], arg2[i], parameters[0], parameters[1], parameters[2]) and sum the squares of those values with i∈[0,n).

      Parameters:
      rf - the real-valued function whose sum of squares should be computed
      args - an array of values for each argument, the last of which is the parameters array
      Returns:
      the sum of the squares
    • sumSquares

      public static double sumSquares(RealValuedFunctionVA rf, LMA.Mode mode, double[]... args)
      Compute the sum of the squares of a real-valued function giving various arguments, treating some arguments specially. The arguments appear first in the function calls, followed by the parameters. For the ith term in the sum, the parameters are always the same while the arguments, which vary with an index i, are given by args[0][i], args[1][i], etc., with the last args array representing the parameters. The values summed are the squares of each term.

      The terms that are summed depend on the mode.

      • If the mode is NORMAL, all arguments are passed to the function. I.e., the function's arguments for index i are args[0][i], args[1][i], ... args[args.length-2][i], ... parameters[0], parameters[1] ... where the array parameters is equal to args[args.length-1].
      • If the mode is LEAST_SQUARES, the first argument is not passed to the function. Instead, that argument is treated as an array y and the arguments to the function are the remaining arguments and the parameters. The ith term becomes yi - fi where fi is the value of the function given the other arguments and the parameters.
      • If the mode is WEIGHTED_LEAST_SQUARES, the first two arguments are not passed to the function. Rather, the first represents the values of y as for the LEAST_SQUARES case and the second represents a divisor. The term squared will be (yi - fi) / σi where yi is the value of the first argument array at index i, fi is the result of evaluating the real-valued function with the other arguments and the parameters, and σi is the value of the second argument array at index i.

      For example, if parameters is an array of length 3, and arg1 and arg2 are arrays of length n, then the sumSquares(rf, Mode.LEAST_SQUARES arg1, arg2, parameters) will evaluate arg1[i] - rf.valueAt(arg2[i], parameters[0], parameters[1], parameters[2]) and sum the squares of those values for i∈[0,n). Similarly, sumSquares(rf, Mode.WEIGHTED_LEAST_SQUARES arg1, arg2, arg3, parameters) will evaluate (arg1[i] - rf.valueAt(arg3[i], parameters[0], parameters[1], parameters[2]))/arg2[i] and sum the squares of those values for i∈[0,n).

      Parameters:
      rf - the real-valued function whose sum of squares should be computed
      mode - the mode (NORMAL, LEAST_SQUARES, WEIGHTED_LEAST_SQUARES)
      args - an array of values for each argument, the last of which is the parameters array used in each function call
      Returns:
      sum of the squares
    • findMin

      public static double findMin(RealValuedFunctionVA rf, double[] guess, double lambda, double nu, double limit, int iterationLimit, double[]... args)
      Find parameters that minimize the sum of squares of a real-valued function with multiple arguments. The quantity minimized is the sum of the squares of a sequence of values. The length of the sequence is the length of the arrays specified by the variable-argument list args. For a given index into these arrays, rf is computed with its first arguments provided by the args arrays and its final arguments provided by a parameters array, initially set to the value of the 'guess' argument.

      For example, if rf takes 4 arguments, and one calls findMin(rf,guess, 5.0, 1.5, 0.0001, 0, args1, args2) where guess is an array with 2 elements, then the values whose squares will be summed are given by rf.valueAt(args1[i], args2[i], guess[0], guess[1]) for each value of i in [0, args1.[0].length). The parameter λ in the Levenberg-Marquardt algorithm has the property that, when it is zero the algorithm behaves like the Gauss-Newton algorithm and when it is large, it behaves like the steepest-descent algorithm with some scaling so that larger increments occur along the direction in which the gradient is smallest.

      Parameters:
      rf - the real-valued function
      guess - an initial guess, also used to store the results
      lambda - the initial value of the Levenberg-Marquardt parameter λ, which must be non-negative
      nu - the Levenberg-Marquardt parameter ν, which must be larger than 1.0
      limit - the convergence limit for the sum of the squares
      iterationLimit - the maximum number of iterations; 0 or negative if there is no limit
      args - arrays of arguments (all arrays must be the same length)
      Returns:
      the sum of the squares with parameters chosen to approximate the minimum value.
      Throws:
      LMA.ConvergenceException - the method did not converge (for example, because an iteration limit was set to too small a value)
    • findMin

      public static double findMin(RealValuedFunctionVA rf, LMA.Mode mode, double[] guess, double lambda, double nu, double limit, int iterationLimit, double[]... args)
      Find parameters that minimize the sum of squares of a real-valued function with multiple arguments, specifying a mode. The quantity minimized is the sum of the squares of a sequence of values. The length of the sequence is the length of the arrays specified by the variable-argument list args. For a given index into these arrays, rf is computed with its first arguments provided by the args arrays and its final arguments provided by a parameters array, initially set to the value of the 'guess' argument.

      For example, if rf takes 4 arguments, and one calls findMin(rf,guess, 5.0, 1.5, 0.0001, 0, args1, args2) where guess is an array with 2 elements, then the values whose squares will be summed are given by rf.valueAt(args1[i], args2[i], guess[0], guess[1]) for each value of i in [0, args1.[0].length). The parameter λ in the Levenberg-Marquardt algorithm has the property that, when it is zero the algorithm behaves like the Gauss-Newton algorithm and when it is large, it behaves like the steepest-descent algorithm with some scaling so that larger increments occur along the direction in which the gradient is smallest.

      Parameters:
      rf - the real-valued function
      mode - the LMA mode (LMA.Mode.NORMAL, LMA.Mode.LEAST_SQUARES, LMA.Mode.WEIGHTED_LEAST_SQUARES)
      guess - an initial guess, also used to store the results
      lambda - the initial value of the Levenberg-Marquardt parameter λ, which must be non-negative
      nu - the Levenberg-Marquardt parameter ν, which must be larger than 1.0
      limit - the convergence limit for the sum of the squares
      iterationLimit - the maximum number of iterations; 0 or negative if there is no limit
      args - arrays of arguments (all arrays must be the same length)
      Returns:
      the sum of the squares with parameters chosen to approximate the minimum value.
      Throws:
      LMA.ConvergenceException - the method did not converge (for example, because an iteration limit was set to too small a value)