Class LevenbergMarquardtOptimizer
- All Implemented Interfaces:
LeastSquaresOptimizer
This implementation should work even for over-determined systems (i.e. systems having more point than equations). Over-determined systems are solved by ignoring the point 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, the use of inherited convergence checker 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:
- Argonne National Laboratory. MINPACK project. March 1980
- Burton S. Garbow
- Kenneth E. Hillstrom
- Jorge J. More
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:
|
- Since:
- 3.3
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static class
Holds internal data.Nested classes/interfaces inherited from interface org.apache.commons.math3.fitting.leastsquares.LeastSquaresOptimizer
LeastSquaresOptimizer.Optimum
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final double
Desired relative error in the sum of squares.private final double
Positive input variable used in determining the initial step bound.private final double
Desired max cosine on the orthogonality between the function vector and the columns of the jacobian.private final double
Desired relative error in the approximate solution parameters.private final double
Threshold for QR ranking.private static final double
Twice the "epsilon machine". -
Constructor Summary
ConstructorsConstructorDescriptionDefault constructor.LevenbergMarquardtOptimizer
(double initialStepBoundFactor, double costRelativeTolerance, double parRelativeTolerance, double orthoTolerance, double qrRankingThreshold) Construct an instance with all parameters specified. -
Method Summary
Modifier and TypeMethodDescriptionprivate void
determineLMDirection
(double[] qy, double[] diag, double[] lmDiag, LevenbergMarquardtOptimizer.InternalData internalData, int solvedCols, double[] work, double[] lmDir) Solve a*x = b and d*x = 0 in the least squares sense.private double
determineLMParameter
(double[] qy, double delta, double[] diag, LevenbergMarquardtOptimizer.InternalData internalData, int solvedCols, double[] work1, double[] work2, double[] work3, double[] lmDir, double lmPar) Determines the Levenberg-Marquardt parameter.double
Gets the value of a tuning parameter.double
Gets the value of a tuning parameter.double
Gets the value of a tuning parameter.double
Gets the value of a tuning parameter.double
Gets the value of a tuning parameter.optimize
(LeastSquaresProblem problem) Solve the non-linear least squares problem.qrDecomposition
(RealMatrix jacobian, int solvedCols) Decompose a matrix A as A.P = Q.R using Householder transforms.private void
qTy
(double[] y, LevenbergMarquardtOptimizer.InternalData internalData) Compute the product Qt.y for some Q.R.withCostRelativeTolerance
(double newCostRelativeTolerance) withInitialStepBoundFactor
(double newInitialStepBoundFactor) withOrthoTolerance
(double newOrthoTolerance) Modifies the given parameter.withParameterRelativeTolerance
(double newParRelativeTolerance) withRankingThreshold
(double newQRRankingThreshold)
-
Field Details
-
TWO_EPS
private static final double TWO_EPSTwice the "epsilon machine". -
initialStepBoundFactor
private final double initialStepBoundFactorPositive input variable used in determining the initial step bound. -
costRelativeTolerance
private final double costRelativeToleranceDesired relative error in the sum of squares. -
parRelativeTolerance
private final double parRelativeToleranceDesired relative error in the approximate solution parameters. -
orthoTolerance
private final double orthoToleranceDesired max cosine on the orthogonality between the function vector and the columns of the jacobian. -
qrRankingThreshold
private final double qrRankingThresholdThreshold for QR ranking.
-
-
Constructor Details
-
LevenbergMarquardtOptimizer
public LevenbergMarquardtOptimizer()Default constructor.The default values for the algorithm settings are:
- Initial step bound factor: 100
- Cost relative tolerance: 1e-10
- Parameters relative tolerance: 1e-10
- Orthogonality tolerance: 1e-10
- QR ranking threshold:
Precision.SAFE_MIN
-
LevenbergMarquardtOptimizer
public LevenbergMarquardtOptimizer(double initialStepBoundFactor, double costRelativeTolerance, double parRelativeTolerance, double orthoTolerance, double qrRankingThreshold) Construct an instance with all parameters specified.- Parameters:
initialStepBoundFactor
- initial step bound factorcostRelativeTolerance
- cost relative toleranceparRelativeTolerance
- parameters relative toleranceorthoTolerance
- orthogonality toleranceqrRankingThreshold
- threshold in the QR decomposition. Columns with a 2 norm less than this threshold are considered to be all 0s.
-
-
Method Details
-
withInitialStepBoundFactor
- Parameters:
newInitialStepBoundFactor
- Positive input variable used in determining the initial step bound. This bound is set to the product of initialStepBoundFactor and the euclidean norm ofdiag * x
if non-zero, or else tonewInitialStepBoundFactor
itself. In most cases factor should lie in the interval(0.1, 100.0)
.100
is a generally recommended value. of the matrix is reduced.- Returns:
- a new instance.
-
withCostRelativeTolerance
- Parameters:
newCostRelativeTolerance
- Desired relative error in the sum of squares.- Returns:
- a new instance.
-
withParameterRelativeTolerance
- Parameters:
newParRelativeTolerance
- Desired relative error in the approximate solution parameters.- Returns:
- a new instance.
-
withOrthoTolerance
Modifies the given parameter.- Parameters:
newOrthoTolerance
- Desired max cosine on the orthogonality between the function vector and the columns of the Jacobian.- Returns:
- a new instance.
-
withRankingThreshold
- Parameters:
newQRRankingThreshold
- Desired threshold for QR ranking. If the squared norm of a column vector is smaller or equal to this threshold during QR decomposition, it is considered to be a zero vector and hence the rank of the matrix is reduced.- Returns:
- a new instance.
-
getInitialStepBoundFactor
public double getInitialStepBoundFactor()Gets the value of a tuning parameter.- Returns:
- the parameter's value.
- See Also:
-
getCostRelativeTolerance
public double getCostRelativeTolerance()Gets the value of a tuning parameter.- Returns:
- the parameter's value.
- See Also:
-
getParameterRelativeTolerance
public double getParameterRelativeTolerance()Gets the value of a tuning parameter.- Returns:
- the parameter's value.
- See Also:
-
getOrthoTolerance
public double getOrthoTolerance()Gets the value of a tuning parameter.- Returns:
- the parameter's value.
- See Also:
-
getRankingThreshold
public double getRankingThreshold()Gets the value of a tuning parameter.- Returns:
- the parameter's value.
- See Also:
-
optimize
Solve the non-linear least squares problem.- Specified by:
optimize
in interfaceLeastSquaresOptimizer
- Parameters:
problem
- the problem definition, including model function and convergence criteria.- Returns:
- The optimum.
-
determineLMParameter
private double determineLMParameter(double[] qy, double delta, double[] diag, LevenbergMarquardtOptimizer.InternalData internalData, int solvedCols, double[] work1, double[] work2, double[] work3, double[] lmDir, double lmPar) Determines 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:
- Argonne National Laboratory. MINPACK project. March 1980
- Burton S. Garbow
- Kenneth E. Hillstrom
- Jorge J. More
Luc Maisonobe did the Java translation.
- Parameters:
qy
- Array containing qTy.delta
- Upper bound on the euclidean norm of diagR * lmDir.diag
- Diagonal matrix.internalData
- Data (modified in-place in this method).solvedCols
- Number of solved point.work1
- work arraywork2
- work arraywork3
- work arraylmDir
- the "returned" LM direction will be stored in this array.lmPar
- the value of the LM parameter from the previous iteration.- Returns:
- the new LM parameter
-
determineLMDirection
private void determineLMDirection(double[] qy, double[] diag, double[] lmDiag, LevenbergMarquardtOptimizer.InternalData internalData, int solvedCols, double[] work, double[] lmDir) 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:
- Argonne National Laboratory. MINPACK project. March 1980
- Burton S. Garbow
- Kenneth E. Hillstrom
- Jorge J. More
Luc Maisonobe did the Java translation.
- Parameters:
qy
- array containing qTydiag
- diagonal matrixlmDiag
- diagonal elements associated with lmDirinternalData
- Data (modified in-place in this method).solvedCols
- Number of sloved point.work
- work arraylmDir
- the "returned" LM direction is stored in this array
-
qrDecomposition
private LevenbergMarquardtOptimizer.InternalData qrDecomposition(RealMatrix jacobian, int solvedCols) throws ConvergenceException 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.
- Parameters:
jacobian
- Weighted Jacobian matrix at the current point.solvedCols
- Number of solved point.- Returns:
- data used in other methods of this class.
- Throws:
ConvergenceException
- if the decomposition cannot be performed.
-
qTy
Compute the product Qt.y for some Q.R. decomposition.- Parameters:
y
- vector to multiply (will be overwritten with the result)internalData
- Data.
-