1 // This file is part of Eugenio, a lightweight C++ template library 2 // for linear algebra. 3 // 4 // Copyright (C) 2009 Thomas Capricelli <orzel (a] 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
