If you are looking for a general-purpose __sparse__ Levenberg-Marquardt C/C++
implementation, please have a look at sparseLM.

# Introduction

This site provides GPL native ANSI C implementations
of the Levenberg-Marquardt optimization algorithm,
usable also from C++, Matlab, Perl,
Python, Haskell and
Tcl and explains their use.
Both __unconstrained__ and __constrained__ (under linear equations, inequality and box constraints) Levenberg-Marquardt
variants are included. The Levenberg-Marquardt (LM)
algorithm is an iterative technique that finds a local minimum of a function that is expressed as the
sum of squares of nonlinear functions. It has become a standard technique for nonlinear least-squares
problems and can be thought of as a combination of steepest descent
and the Gauss-Newton method.
When the current solution is far from the correct one, the algorithm behaves like a steepest descent
method: slow, but guaranteed to converge. When the current solution is close to the correct solution,
it becomes a Gauss-Newton method.

# Motivation

The `lmder` routine from Minpack, written 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.
The reasons presented above led to the development of the `levmar` package which includes C implementations
of LM flavors that are also usable with C++.

# Technical Overview

`levmar` includes double and single precision LM C/C++ 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.
There is also a short note, providing a quick overview of the material in the lecture notes.

To deal with linear equation constraints, `levmar` employs variable elimination based on QR factorization,
as described in ch. 15 of the book
Numerical Optimization
by Nocedal and Wright. For the box-constrained case, `levmar` implements the algorithm proposed
by C. Kanzow, N. Yamashita and M. Fukushima,
Levenberg-Marquardt
methods for constrained nonlinear equations with strong local convergence properties,
Journal of Computational and Applied Mathematics 172, 2004, pp. 375-397.

`levmar` provides the following two options regarding the solution of the linear systems formed by the
augmented normal equations:

- If you have LAPACK (or an equivalent vendor library
such as Intel's MKL, AMD's AMCL, Sun's performance library, IBM's ESSL, SGI's SCSL, NAG, ...),
the included LAPACK-based solvers can be used. This is the default option. The employed solver
is based on the LU decomposition. Additionally, for experimenting with other approaches, linear
solvers based on the Cholesky and QR decompositions have been supplied.
- If LAPACK is unavailable, a LAPACK-free, LU-based linear systems solver can be used by undefining
`HAVE_LAPACK`in`levmar.h`.

Use of LAPACK or an equivalent vendor library is strongly recommended; if none is installed at your site
I suggest getting CLAPACK, the f2c'ed version of LAPACK. MSWin
users have the additional option of downloading precompiled LAPACK/BLAS libraries from
here.
You might also consider combining CLAPACK with ATLAS,
(the automatically tuned BLAS implementation) or
GotoBLAS (K. Goto's high-performance BLAS).
On the other hand, LAPACK's use is not mandatory for compiling the unconstrained routines
and the second option makes `levmar` totally self-contained. The linear equation constrained
routines, however, cannot be compiled without LAPACK.

`levmar` also has support for PLASMA, the parallel
linear algebra for homogeneous multi-core architectures. Using PLASMA can accelerate the solution of
the underlying linear systems, thus improving the performance of large optimization problems.

Interfaces for using `levmar` from high-level programming environments & languages such as
Matlab, Perl
Python, Haskell and
Tcl
are also available; please refer to the FAQ for more details.

# Available Functions

`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

`dlevmar_bleic_der()`: double precision, box, linear equation & inequality constraints, analytic Jacobian`dlevmar_bleic_dif()`: double precision, box, linear equation & inequality constraints, finite difference approximated Jacobian`slevmar_bleic_der()`: single precision, box, linear equation & inequality constraints, analytic Jacobian`slevmar_bleic_dif()`: single precision, box, linear equation & inequality constraints, finite difference approximated Jacobian

- Convenience wrappers
`xlevmar_blic_der()`/`xlevmar_blic_dif()`,`xlevmar_leic_der()`/`xlevmar_leic_dif()`&`xlevmar_lic_der()`/`xlevmar_lic_dif()`to`xlevmar_bleic_der()`/`xlevmar_bleic_dif()`are also provided.

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 basically 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]<=p[i]<=ub[i], linear equality constrains of the form A*p=b with A k1xm and b k1x1 and
linear inequality constraints C*p>=d with C k2xm and d k2x1, can be enforced on the minimizer.
More details on the unconstrained LM algorithm implemented by `levmar` can be found in this note.

Briefly, the arguments of the functions are as follows: pointers to routines evaluating the vector function f and its
Jacobian (if applicable), pointers to the initial estimate of the parameter vector p and the measurement vector x, the
dimension m of p, the dimension n of x, the maximum number of iterations, a pointer to a 3 element array whose elements
specify certain minimization options, a pointer to an array into the elements of which various pieces of information regarding
the result of minimization will be returned, a pointer to working memory, a pointer to a covariance matrix and a pointer
to application-specific data structures
that might be necessary for computing the function to be minimized and its derivatives. More details can be found below.
Additionally, the included `lmdemo.c` sample program gives working examples of minimizing several nonlinear functions.
The exact prototypes of `dlevmar_der()`, `dlevmar_dif()` are given next, along with a description of
each argument. `slevmar_der()` and `slevmar_dif()` are identical, except that doubles are changed to floats.
I and O in the descriptions below denote input and output arguments, respectively. Constrained optimization routines
have very similar arguments, for detailed descriptions please see the comments in the code.

`dlevmar_der()`

```
.:: toggle display ::.
```

`dlevmar_dif()`

```
.:: toggle display ::.
```

Note that passing `NULL` as the value of the last four arguments of both functions results in default values being
used. Consult Madsen et al's lecture notes
for details on the roles of `opts` and `info` arguments. Argument `work` is meant to be used to
avoid the overhead associated
with repeatedly allocating and freeing memory chunks of the same size, when several minimizations of the same dimension are
carried out. Instead of letting the functions allocate the required memory themselves, you can use the macros `LM_DER_WORKSZ`
and `LM_DIF_WORKSZ` to calculate the appropriate memory size, allocate it and pass it to each invocation. `lmdemo.c`
provides such an example. The last argument (i.e. `adata`) is intended to help avoid direct use of globals in the
routines computing the function to be minimized and its Jacobian. A structure containing pointers to appropriate data
structures can be set up and a pointer to it can be passed to the LM function which then passes it uninterpreted to each
call of the user-supplied routines.

# Contact Address

If you find this package useful or have any comments/questions/suggestions, please contact me at

Be warned that although I try to reply to most messages, I might take long to do so.

In case that you use `levmar` in your published work, please include a reference/acknowledgement to this site:
[ bibtex entry ].

hits since Thu Nov 10 15:08:15 EET 2005