levmar.h File Reference

Levenberg-Marquardt for nonlinear least squares. More...

#include <cstddef>
#include <memory>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/lu.h"
#include "line/util/matrix.h"

Include dependency graph for levmar.h:

Go to the source code of this file.

Classes
struct	line::LevmarOptions< T >
	Tuning of the Levenberg-Marquardt iteration. More...
struct	line::LevmarResult< T >
	Outcome of a least-squares solve. More...

Namespaces
namespace	line

Functions
template<class T>
LevmarOptions< T >	line::levmar_defaults ()
	MINPACK-like defaults, with a central-difference step of eps^(1/3).
template<class T, class F>
Matrix< T >	line::levmar_jacobian_fd (F f, const std::vector< T > &x, std::size_t m, const T &diff_step)
	Central-difference Jacobian of r at x.
template<class T, class F, class J>
LevmarResult< T >	line::levmar_jac (F f, J jac, const std::vector< T > &x0, std::size_t m, const LevmarOptions< T > &opt)
	Levenberg-Marquardt with a caller-supplied Jacobian.
template<class T, class F>
LevmarResult< T >	line::levmar (F f, const std::vector< T > &x0, std::size_t m, const LevmarOptions< T > &opt)
	Levenberg-Marquardt with a central-difference Jacobian.
template<class T, class F>
LevmarResult< T >	line::levmar (F f, const std::vector< T > &x0, std::size_t m)
	levmar with the default tuning.

Detailed Description

Levenberg-Marquardt for nonlinear least squares.

Minimizes S(x) = sum_i r_i(x)^2 for a caller-supplied residual map r : R^n -> R^m. This is the workhorse behind the moment-matching fits in line/api/mam: every one of them states its target as a vector of relative errors (moment_fitted/moment_target - 1) that would be zero at an exact match, which is exactly the shape LM wants.

ACCEPTANCE CONTRACT. Substituting an optimizer is not a transcription. The caller must NOT expect the iterates, the iteration count, or the last digits of the answer to agree with MATLAB's fmincon / fminsearch / optimproblem solve, which are different algorithms with different termination rules and, in the GlobalSearch cases, a random multi-start. What a caller may rely on is stated per entry point in terms of the specification: the achieved objective value, which is returned so it can be compared against any other optimizer's on the same input.

Implementation notes:

• the step solves (J^T J + mu I) dx = -J^T r with mu = lambda max_j (J^T J)_jj, the uniform damping of Madsen, Nielsen and Tingleff, which is scaled to the problem yet insensitive to a column of J that is only differencing noise (see the note in levmar_jac on why Marquardt's per-column damping cannot be used with a numeric Jacobian);
• lambda is multiplied by lambda_increase on a rejected step and by lambda_decrease on an accepted one;
• the Jacobian defaults to central differences with a relative step, which costs 2n residual evaluations per iteration and is second-order accurate; an analytic Jacobian is supplied through levmar_jac.

Deterministic: no random restarts, no global state, no exit(), no output. Failure to converge is reported through LevmarResult::converged, never thrown, since a partially converged fit is still usable and the caller is the one that knows the tolerance it needs.

Gated on transcendental arithmetic: the method stops on tolerances, so it is meaningless at exact arithmetic (which would run to the iteration cap carrying ever larger rationals).

Definition in file levmar.h.