| 1 | // This file is part of Eigen, 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 | /**
|
|---|
| 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
|
|---|
