org.apache.commons.math.estimation
Class LevenbergMarquardtEstimator

java.lang.Object
  extended by org.apache.commons.math.estimation.AbstractEstimator
      extended by org.apache.commons.math.estimation.LevenbergMarquardtEstimator
All Implemented Interfaces:
Serializable, Estimator

Deprecated. as of 2.0, everything in package org.apache.commons.math.estimation has been deprecated and replaced by package org.apache.commons.math.optimization.general

@Deprecated
public class LevenbergMarquardtEstimator
extends AbstractEstimator
implements Serializable

This class solves a least squares problem.

This implementation should work even for over-determined systems (i.e. systems having more variables than equations). Over-determined systems are solved by ignoring the variables which have the smallest impact according to their jacobian column norm. Only the rank of the matrix and some loop bounds are changed to implement this.

The resolution engine is a simple translation of the MINPACK lmder routine with minor changes. The changes include the over-determined resolution and the Q.R. decomposition which has been rewritten following the algorithm described in the P. Lascaux and R. Theodor book Analyse numérique matricielle appliquée à l'art de l'ingénieur, Masson 1986.

The authors of the original fortran version are:

The redistribution policy for MINPACK is available here, for convenience, it is reproduced below.

Minpack Copyright Notice (1999) University of Chicago. All rights reserved
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
  1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
  2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
  3. The end-user documentation included with the redistribution, if any, must include the following acknowledgment: This product includes software developed by the University of Chicago, as Operator of Argonne National Laboratory. Alternately, this acknowledgment may appear in the software itself, if and wherever such third-party acknowledgments normally appear.
  4. WARRANTY DISCLAIMER. THE SOFTWARE IS SUPPLIED "AS IS" WITHOUT WARRANTY OF ANY KIND. THE COPYRIGHT HOLDER, THE UNITED STATES, THE UNITED STATES DEPARTMENT OF ENERGY, AND THEIR EMPLOYEES: (1) DISCLAIM ANY WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, TITLE OR NON-INFRINGEMENT, (2) DO NOT ASSUME ANY LEGAL LIABILITY OR RESPONSIBILITY FOR THE ACCURACY, COMPLETENESS, OR USEFULNESS OF THE SOFTWARE, (3) DO NOT REPRESENT THAT USE OF THE SOFTWARE WOULD NOT INFRINGE PRIVATELY OWNED RIGHTS, (4) DO NOT WARRANT THAT THE SOFTWARE WILL FUNCTION UNINTERRUPTED, THAT IT IS ERROR-FREE OR THAT ANY ERRORS WILL BE CORRECTED.
  5. LIMITATION OF LIABILITY. IN NO EVENT WILL THE COPYRIGHT HOLDER, THE UNITED STATES, THE UNITED STATES DEPARTMENT OF ENERGY, OR THEIR EMPLOYEES: BE LIABLE FOR ANY INDIRECT, INCIDENTAL, CONSEQUENTIAL, SPECIAL OR PUNITIVE DAMAGES OF ANY KIND OR NATURE, INCLUDING BUT NOT LIMITED TO LOSS OF PROFITS OR LOSS OF DATA, FOR ANY REASON WHATSOEVER, WHETHER SUCH LIABILITY IS ASSERTED ON THE BASIS OF CONTRACT, TORT (INCLUDING NEGLIGENCE OR STRICT LIABILITY), OR OTHERWISE, EVEN IF ANY OF SAID PARTIES HAS BEEN WARNED OF THE POSSIBILITY OF SUCH LOSS OR DAMAGES.

    Since:
    1.2
    Version:
    $Revision: 990655 $ $Date: 2010-08-29 23:49:40 +0200 (dim. 29 août 2010) $
    See Also:
    Serialized Form

    Field Summary
    private  double[] beta
              Deprecated. Coefficients of the Householder transforms vectors.
    private  double costRelativeTolerance
              Deprecated. Desired relative error in the sum of squares.
    private  double[] diagR
              Deprecated. Diagonal elements of the R matrix in the Q.R.
    private  double initialStepBoundFactor
              Deprecated. Positive input variable used in determining the initial step bound.
    private  double[] jacNorm
              Deprecated. Norms of the columns of the jacobian matrix.
    private  double[] lmDir
              Deprecated. Parameters evolution direction associated with lmPar.
    private  double lmPar
              Deprecated. Levenberg-Marquardt parameter.
    private  double orthoTolerance
              Deprecated. Desired max cosine on the orthogonality between the function vector and the columns of the jacobian.
    private  double parRelativeTolerance
              Deprecated. Desired relative error in the approximate solution parameters.
    private  int[] permutation
              Deprecated. Columns permutation array.
    private  int rank
              Deprecated. Rank of the jacobian matrix.
    private static long serialVersionUID
              Deprecated. Serializable version identifier
    private  int solvedCols
              Deprecated. Number of solved variables.
     
    Fields inherited from class org.apache.commons.math.estimation.AbstractEstimator
    cols, cost, DEFAULT_MAX_COST_EVALUATIONS, jacobian, measurements, parameters, residuals, rows
     
    Constructor Summary
    LevenbergMarquardtEstimator()
              Deprecated. Build an estimator for least squares problems.
     
    Method Summary
    private  void determineLMDirection(double[] qy, double[] diag, double[] lmDiag, double[] work)
              Deprecated. Solve a*x = b and d*x = 0 in the least squares sense.
    private  void determineLMParameter(double[] qy, double delta, double[] diag, double[] work1, double[] work2, double[] work3)
              Deprecated. Determine the Levenberg-Marquardt parameter.
     void estimate(EstimationProblem problem)
              Deprecated. Solve an estimation problem using the Levenberg-Marquardt algorithm.
    private  void qrDecomposition()
              Deprecated. Decompose a matrix A as A.P = Q.R using Householder transforms.
    private  void qTy(double[] y)
              Deprecated. Compute the product Qt.y for some Q.R.
     void setCostRelativeTolerance(double costRelativeTolerance)
              Deprecated. Set the desired relative error in the sum of squares.
     void setInitialStepBoundFactor(double initialStepBoundFactor)
              Deprecated. Set the positive input variable used in determining the initial step bound.
     void setOrthoTolerance(double orthoTolerance)
              Deprecated. Set the desired max cosine on the orthogonality.
     void setParRelativeTolerance(double parRelativeTolerance)
              Deprecated. Set the desired relative error in the approximate solution parameters.
     
    Methods inherited from class org.apache.commons.math.estimation.AbstractEstimator
    getChiSquare, getCostEvaluations, getCovariances, getJacobianEvaluations, getRMS, guessParametersErrors, incrementJacobianEvaluationsCounter, initializeEstimate, setMaxCostEval, updateJacobian, updateResidualsAndCost
     
    Methods inherited from class java.lang.Object
    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
     

    Field Detail

    serialVersionUID

    private static final long serialVersionUID
    Deprecated. 
    Serializable version identifier

    See Also:
    Constant Field Values

    solvedCols

    private int solvedCols
    Deprecated. 
    Number of solved variables.


    diagR

    private double[] diagR
    Deprecated. 
    Diagonal elements of the R matrix in the Q.R. decomposition.


    jacNorm

    private double[] jacNorm
    Deprecated. 
    Norms of the columns of the jacobian matrix.


    beta

    private double[] beta
    Deprecated. 
    Coefficients of the Householder transforms vectors.


    permutation

    private int[] permutation
    Deprecated. 
    Columns permutation array.


    rank

    private int rank
    Deprecated. 
    Rank of the jacobian matrix.


    lmPar

    private double lmPar
    Deprecated. 
    Levenberg-Marquardt parameter.


    lmDir

    private double[] lmDir
    Deprecated. 
    Parameters evolution direction associated with lmPar.


    initialStepBoundFactor

    private double initialStepBoundFactor
    Deprecated. 
    Positive input variable used in determining the initial step bound.


    costRelativeTolerance

    private double costRelativeTolerance
    Deprecated. 
    Desired relative error in the sum of squares.


    parRelativeTolerance

    private double parRelativeTolerance
    Deprecated. 
    Desired relative error in the approximate solution parameters.


    orthoTolerance

    private double orthoTolerance
    Deprecated. 
    Desired max cosine on the orthogonality between the function vector and the columns of the jacobian.

    Constructor Detail

    LevenbergMarquardtEstimator

    public LevenbergMarquardtEstimator()
    Deprecated. 
    Build an estimator for least squares problems.

    The default values for the algorithm settings are:

    Method Detail

    setInitialStepBoundFactor

    public void setInitialStepBoundFactor(double initialStepBoundFactor)
    Deprecated. 
    Set the positive input variable used in determining the initial step bound. This bound is set to the product of initialStepBoundFactor and the euclidean norm of diag*x if nonzero, or else to initialStepBoundFactor itself. In most cases factor should lie in the interval (0.1, 100.0). 100.0 is a generally recommended value

    Parameters:
    initialStepBoundFactor - initial step bound factor
    See Also:
    estimate(org.apache.commons.math.estimation.EstimationProblem)

    setCostRelativeTolerance

    public void setCostRelativeTolerance(double costRelativeTolerance)
    Deprecated. 
    Set the desired relative error in the sum of squares.

    Parameters:
    costRelativeTolerance - desired relative error in the sum of squares
    See Also:
    estimate(org.apache.commons.math.estimation.EstimationProblem)

    setParRelativeTolerance

    public void setParRelativeTolerance(double parRelativeTolerance)
    Deprecated. 
    Set the desired relative error in the approximate solution parameters.

    Parameters:
    parRelativeTolerance - desired relative error in the approximate solution parameters
    See Also:
    estimate(org.apache.commons.math.estimation.EstimationProblem)

    setOrthoTolerance

    public void setOrthoTolerance(double orthoTolerance)
    Deprecated. 
    Set the desired max cosine on the orthogonality.

    Parameters:
    orthoTolerance - desired max cosine on the orthogonality between the function vector and the columns of the jacobian
    See Also:
    estimate(org.apache.commons.math.estimation.EstimationProblem)

    estimate

    public void estimate(EstimationProblem problem)
                  throws EstimationException
    Deprecated. 
    Solve an estimation problem using the Levenberg-Marquardt algorithm.

    The algorithm used is a modified Levenberg-Marquardt one, based on the MINPACK lmder routine. The algorithm settings must have been set up before this method is called with the setInitialStepBoundFactor(double), AbstractEstimator.setMaxCostEval(int), setCostRelativeTolerance(double), setParRelativeTolerance(double) and setOrthoTolerance(double) methods. If these methods have not been called, the default values set up by the constructor will be used.

    The authors of the original fortran function are:

    Luc Maisonobe did the Java translation.

    Specified by:
    estimate in interface Estimator
    Specified by:
    estimate in class AbstractEstimator
    Parameters:
    problem - estimation problem to solve
    Throws:
    EstimationException - if convergence cannot be reached with the specified algorithm settings or if there are more variables than equations
    See Also:
    setInitialStepBoundFactor(double), setCostRelativeTolerance(double), setParRelativeTolerance(double), setOrthoTolerance(double)

    determineLMParameter

    private void determineLMParameter(double[] qy,
                                      double delta,
                                      double[] diag,
                                      double[] work1,
                                      double[] work2,
                                      double[] work3)
    Deprecated. 
    Determine the Levenberg-Marquardt parameter.

    This implementation is a translation in Java of the MINPACK lmpar routine.

    This method sets the lmPar and lmDir attributes.

    The authors of the original fortran function are:

    Luc Maisonobe did the Java translation.

    Parameters:
    qy - array containing qTy
    delta - upper bound on the euclidean norm of diagR * lmDir
    diag - diagonal matrix
    work1 - work array
    work2 - work array
    work3 - work array

    determineLMDirection

    private void determineLMDirection(double[] qy,
                                      double[] diag,
                                      double[] lmDiag,
                                      double[] work)
    Deprecated. 
    Solve a*x = b and d*x = 0 in the least squares sense.

    This implementation is a translation in Java of the MINPACK qrsolv routine.

    This method sets the lmDir and lmDiag attributes.

    The authors of the original fortran function are:

    Luc Maisonobe did the Java translation.

    Parameters:
    qy - array containing qTy
    diag - diagonal matrix
    lmDiag - diagonal elements associated with lmDir
    work - work array

    qrDecomposition

    private void qrDecomposition()
                          throws EstimationException
    Deprecated. 
    Decompose a matrix A as A.P = Q.R using Householder transforms.

    As suggested in the P. Lascaux and R. Theodor book Analyse numérique matricielle appliquée à l'art de l'ingénieur (Masson, 1986), instead of representing the Householder transforms with uk unit vectors such that:

     Hk = I - 2uk.ukt
     
    we use k non-unit vectors such that:
     Hk = I - betakvk.vkt
     
    where vk = ak - alphak ek. The betak coefficients are provided upon exit as recomputing them from the vk vectors would be costly.

    This decomposition handles rank deficient cases since the tranformations are performed in non-increasing columns norms order thanks to columns pivoting. The diagonal elements of the R matrix are therefore also in non-increasing absolute values order.

    Throws:
    EstimationException - if the decomposition cannot be performed

    qTy

    private void qTy(double[] y)
    Deprecated. 
    Compute the product Qt.y for some Q.R. decomposition.

    Parameters:
    y - vector to multiply (will be overwritten with the result)


    Copyright (c) 2003-2013 Apache Software Foundation