#optimization #optimizer #levenberg #marquardt #squares

no-std levenberg-marquardt

Levenberg-Marquardt algorithm built on top of nalgebra

8 releases (5 breaking)

0.6.0 Sep 12, 2020
0.5.2 Jun 7, 2020
0.5.0 Apr 30, 2020
0.4.0 Mar 8, 2020
0.1.0 Jan 5, 2020

#48 in Robotics

Download history 84/week @ 2020-06-03 21/week @ 2020-06-10 17/week @ 2020-06-17 37/week @ 2020-06-24 23/week @ 2020-07-01 39/week @ 2020-07-08 83/week @ 2020-07-15 64/week @ 2020-07-22 158/week @ 2020-07-29 53/week @ 2020-08-05 69/week @ 2020-08-12 54/week @ 2020-08-19 42/week @ 2020-08-26 42/week @ 2020-09-02 56/week @ 2020-09-09 29/week @ 2020-09-16

236 downloads per month
Used in cv

MIT license

180KB
4K SLoC

levenberg-marquardt

Discord Crates.io MIT/Apache docs.rs LoC Tests Lints no_std

Solver for nonlinear least squares problems

The implementation is a port of the classic MINPACK implementation of the Levenberg-Marquardt (LM) algorithm. This version of the algorithm is sometimes referred to as exact LM.

All current unit tests indicate that we achieved identical output (on a floating-point level) to the MINPACK implementation, especially for rank deficient unstable problems. This was mainly useful for testing. The Fortran algorithm was extended with NaN and inf handling, similar to what lmfit does.

The crate offers a feature called minpack-compat which sets floating-point constants to the ones used by MINPACK and removes the termination criterion of "zero residuals". This is necessary for identical output to MINPACK but generally not recommended.

Usage

See the docs for detailed information.

impl LeastSquaresProblem<f64> for Problem {
    // define this trait for the problem you want to solve
}
let problem = Problem::new(initial_params);
let (problem, report) = LevenbergMarquardt::new().minimize(problem);
assert!(report.termination.was_successful());

References

Sofware:

  • The MINPACK Fortran implementation.
  • A C version/update, lmfit.
  • A Python implementation in pwkit.

One original reference for the algorithm seems to be

Moré J.J. (1978) The Levenberg-Marquardt algorithm: Implementation and theory. In: Watson G.A. (eds) Numerical Analysis. Lecture Notes in Mathematics, vol 630. Springer, Berlin, Heidelberg.

by one of the authors of MINPACK.

The algorihm is also described in the form as implemented by this crate in the book "Numerical Optimization" by Nocedal and Wright, chapters 4 and 10.

Dependencies

~3MB
~63K SLoC