levmar

levmar is an implementation of the Levenberg-Marquardt nonlinear least squares algorithms in C/C++.

The lmder routine from Minpack, implemented in the early '80s at the Argonne National Lab, is perhaps the most widely used free implementation of the LM algorithm. lmder is written in FORTRAN77 and over the years has proven to be a reliable piece of software. Considering that FORTRAN routines can be called from C/C++, one might wonder about the motivation for writing a version of LM in C. Well, the problem is that when FORTRAN is called from C, the programmer should be aware of (and conform to) several rules regarding name mangling, argument passing, multidimensional array memory layout, linkage conventions, etc, that are unnatural compared to ordinary C rules. A second reason is that this approach takes for granted that a FORTRAN compiler for the target programming environment is available, which might not necessarily be the case. Another reason has to do with failure to understand the inner workings of a FORTRAN implementation: Occasionally, when it is necessary to precisely understand what the FORTRAN code does, certain pieces of it might seem incomprehensible to programmers without any knowledge of FORTRAN. Automatic FORTRAN to C translators (e.g. f2c) do not solve the problem since the produced C code is pretty illegible to "uninitiated" humans. Moreover, documentation describing the mathematics upon which the implementation is based might be obscure or inaccessible. Last but not least, a candidate LM implementation in C should be free and technically sound. For example, the C variant of the LM algorithm presented in the "Numerical Recipes" book (i.e. mrqmin), is not always a viable choice: Besides its being copyrighted, it is reputed to lack robustness.

For the above reasons, I have developed the levmar package which includes C implementations of LM flavors that are also usable with C++. levmar includes double and single precision LM implementations, both with analytic and finite difference approximated Jacobians. It is provided free of charge, under the terms of the GNU General Public License. The mathematical theory behind unconstrained levmar is described in detail in the lecture notes entitled Methods for Non-Linear Least Squares Problems, by K. Madsen, H.B. Nielsen and O. Tingleff, Technical University of Denmark; Matlab implementations of the algorithms presented in the lecture notes are also available. Note however that the formulation of the minimization problem adopted here is slightly different from that described in the lecture notes.

Function's Use:

levmar offers several user-callable functions obeying the following naming convention: The first letter (d or s) specifies double or single precision and the suffix (_der or _dif) denotes analytic or approximate Jacobian. If present, the lec, bc and blec components imply linear equation, box and simultaneous box and linear equation constraints, respectively. More specifically, levmar includes the functions below:

Unconstrained optimization

dlevmar_der(): double precision, analytic Jacobian
dlevmar_dif(): double precision, finite difference approximated Jacobian
slevmar_der(): single precision, analytic Jacobian
slevmar_dif(): single precision, finite difference approximated Jacobian

Constrained optimization

dlevmar_lec_der(): double precision, linear equation constraints, analytic Jacobian
dlevmar_lec_dif(): double precision, linear equation constraints, finite difference approximated Jacobian
slevmar_lec_der(): single precision, linear equation constraints, analytic Jacobian
slevmar_lec_dif(): single precision, linear equation constraints, finite difference approximated Jacobian

dlevmar_bc_der(): double precision, box constraints, analytic Jacobian
dlevmar_bc_dif(): double precision, box constraints, finite difference approximated Jacobian
slevmar_bc_der(): single precision, box constraints, analytic Jacobian
slevmar_bc_dif(): single precision, box constraints, finite difference approximated Jacobian

dlevmar_blec_der(): double precision, box & linear equation constraints, analytic Jacobian
dlevmar_blec_dif(): double precision, box & linear equation constraints, finite difference approximated Jacobian
slevmar_blec_der(): single precision, box & linear equation constraints, analytic Jacobian
slevmar_blec_dif(): single precision, box & linear equation constraints, finite difference approximated Jacobian

Notice that using finite differences to approximate the Jacobian results in repetitive evaluations of the function to be fitted. Aiming to reduce the total number of these evaluations, the xxxxxxx_dif functions implement secant approximations to the Jacobian using Broyden's rank one updates. All functions solve the same problem, i.e. they seek the parameter vector p that best describes (in terms of the L2 norm) the measurements vector x. More precisely, given a vector function f : R^m --> R^n with n>=m, they compute a p such that f(p) ~= x, i.e. the squared norm ||e||^2=||x-f(p)||^2 is minimized. Also, box constraints of the form lb[i]

What is new in this release:

• This version adds support for diagonal scaling to xlevmar_bc_der(), which can improve convergence when the starting point is far from the true minimizer.
• A linear systems solver supporting parallel Cholesky decomposition with PLASMA, the linear algebra library for multi-core processors.
• Linear solvers have been fixed so that they operate on lower triangles of symmetric matrices, which results in better cache performance.
• The CMake configuration files for building the project have been revised.
• Several other minor changes have been made.

What is new in version 2.5:

• CAUTION FOR PREVIOUS VERSIONS USERS: For better consistency and avoidance of conflicts, the name of levmar's header file was changed from lm.h to levmar.h; please update your source files accordingly.
• Added support for minimization under simultaneous box, linear equation and inequality constraints (see functions xlevmar_bleic_der() & xlevmar_bleic_dif()).
• Implemented convenience wrappers to xlevmar_bleic_der() & xlevmar_bleic_dif() dealing with simpler constrained cases, e.g. xlevmar_blic_der() & xlevmar_blic_dif() support minimization under box and linear inequality constraints only.
• Added a linear systems solver based on the UDUt decomposition (i.e., sqrt-free Cholesky).
• Removed some unnecessary memory copying from most linear solvers.
• Added a new data-fitting test problem (Osborne).
• Made a few other minor changes.

What is new in version 2.4:

• CAUTION FOR PREVIOUS VERSIONS USERS: The size of the info argument (i.e., LM_INFO_SZ) was increased by one to accomodate a new return field (i.e., info[9]) that corresponds to the total number of linear systems solved during the course of the minimization. The indices of previously returned fields in the info array remain unchanged.
• Implemented a more cache-efficient scheme for computing the approximate Hessian J^T*J and J^T*e for small-sized minimization problems.
• Ensured that any working memory retained between invocations of the linear solvers is released upon the termination of levmar routines.
• Ensured that linear solvers employ the minimum required amount of auxiliary memory, avoiding occasional over-allocations.
• Implemented a loop unrolling scheme for speeding up the computation of e=x-hx.
• Fixed a couple of issues with memory alignment on 64 bit systems.
• Added functions for the computation of the coefficient of determination.
• Dealt with a few minor issues.