• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1// This file is part of Eugenio, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2009 Thomas Capricelli <orzel@freehackers.org>
5//
6// This Source Code Form is subject to the terms of the Mozilla
7// Public License v. 2.0. If a copy of the MPL was not distributed
8// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9
10#ifndef EIGEN_NONLINEAROPTIMIZATION_MODULE
11#define EIGEN_NONLINEAROPTIMIZATION_MODULE
12
13#include <vector>
14
15#include <Eigen/Core>
16#include <Eigen/Jacobi>
17#include <Eigen/QR>
18#include <unsupported/Eigen/NumericalDiff>
19
20/** \ingroup Unsupported_modules
21  * \defgroup NonLinearOptimization_Module Non linear optimization module
22  *
23  * \code
24  * #include <unsupported/Eigen/NonLinearOptimization>
25  * \endcode
26  *
27  * This module provides implementation of two important algorithms in non linear
28  * optimization. In both cases, we consider a system of non linear functions. Of
29  * course, this should work, and even work very well if those functions are
30  * actually linear. But if this is so, you should probably better use other
31  * methods more fitted to this special case.
32  *
33  * One algorithm allows to find an extremum of such a system (Levenberg
34  * Marquardt algorithm) and the second one is used to find
35  * a zero for the system (Powell hybrid "dogleg" method).
36  *
37  * This code is a port of minpack (http://en.wikipedia.org/wiki/MINPACK).
38  * Minpack is a very famous, old, robust and well-reknown package, written in
39  * fortran. Those implementations have been carefully tuned, tested, and used
40  * for several decades.
41  *
42  * The original fortran code was automatically translated using f2c (http://en.wikipedia.org/wiki/F2c) in C,
43  * then c++, and then cleaned by several different authors.
44  * The last one of those cleanings being our starting point :
45  * http://devernay.free.fr/hacks/cminpack.html
46  *
47  * Finally, we ported this code to Eigen, creating classes and API
48  * coherent with Eigen. When possible, we switched to Eigen
49  * implementation, such as most linear algebra (vectors, matrices, stable norms).
50  *
51  * Doing so, we were very careful to check the tests we setup at the very
52  * beginning, which ensure that the same results are found.
53  *
54  * \section Tests Tests
55  *
56  * The tests are placed in the file unsupported/test/NonLinear.cpp.
57  *
58  * There are two kinds of tests : those that come from examples bundled with cminpack.
59  * They guaranty we get the same results as the original algorithms (value for 'x',
60  * for the number of evaluations of the function, and for the number of evaluations
61  * of the jacobian if ever).
62  *
63  * Other tests were added by myself at the very beginning of the
64  * process and check the results for levenberg-marquardt using the reference data
65  * on http://www.itl.nist.gov/div898/strd/nls/nls_main.shtml. Since then i've
66  * carefully checked that the same results were obtained when modifiying the
67  * code. Please note that we do not always get the exact same decimals as they do,
68  * but this is ok : they use 128bits float, and we do the tests using the C type 'double',
69  * which is 64 bits on most platforms (x86 and amd64, at least).
70  * I've performed those tests on several other implementations of levenberg-marquardt, and
71  * (c)minpack performs VERY well compared to those, both in accuracy and speed.
72  *
73  * The documentation for running the tests is on the wiki
74  * http://eigen.tuxfamily.org/index.php?title=Tests
75  *
76  * \section API API : overview of methods
77  *
78  * Both algorithms can use either the jacobian (provided by the user) or compute
79  * an approximation by themselves (actually using Eigen \ref NumericalDiff_Module).
80  * The part of API referring to the latter use 'NumericalDiff' in the method names
81  * (exemple: LevenbergMarquardt.minimizeNumericalDiff() )
82  *
83  * The methods LevenbergMarquardt.lmder1()/lmdif1()/lmstr1() and
84  * HybridNonLinearSolver.hybrj1()/hybrd1() are specific methods from the original
85  * minpack package that you probably should NOT use until you are porting a code that
86  *  was previously using minpack. They just define a 'simple' API with default values
87  * for some parameters.
88  *
89  * All algorithms are provided using Two APIs :
90  *     - one where the user inits the algorithm, and uses '*OneStep()' as much as he wants :
91  * this way the caller have control over the steps
92  *     - one where the user just calls a method (optimize() or solve()) which will
93  * handle the loop: init + loop until a stop condition is met. Those are provided for
94  *  convenience.
95  *
96  * As an example, the method LevenbergMarquardt::minimize() is
97  * implemented as follow :
98  * \code
99  * Status LevenbergMarquardt<FunctorType,Scalar>::minimize(FVectorType  &x, const int mode)
100  * {
101  *     Status status = minimizeInit(x, mode);
102  *     do {
103  *         status = minimizeOneStep(x, mode);
104  *     } while (status==Running);
105  *     return status;
106  * }
107  * \endcode
108  *
109  * \section examples Examples
110  *
111  * The easiest way to understand how to use this module is by looking at the many examples in the file
112  * unsupported/test/NonLinearOptimization.cpp.
113  */
114
115#ifndef EIGEN_PARSED_BY_DOXYGEN
116
117#include "src/NonLinearOptimization/qrsolv.h"
118#include "src/NonLinearOptimization/r1updt.h"
119#include "src/NonLinearOptimization/r1mpyq.h"
120#include "src/NonLinearOptimization/rwupdt.h"
121#include "src/NonLinearOptimization/fdjac1.h"
122#include "src/NonLinearOptimization/lmpar.h"
123#include "src/NonLinearOptimization/dogleg.h"
124#include "src/NonLinearOptimization/covar.h"
125
126#include "src/NonLinearOptimization/chkder.h"
127
128#endif
129
130#include "src/NonLinearOptimization/HybridNonLinearSolver.h"
131#include "src/NonLinearOptimization/LevenbergMarquardt.h"
132
133
134#endif // EIGEN_NONLINEAROPTIMIZATION_MODULE
135