1// This file is part of Eigen, a lightweight C++ template library 2// for linear algebra. 3// 4// Copyright (C) 2009 Thomas Capricelli <[email protected]> 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 "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 a least-squares solution of such a system 34 * (Levenberg-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 renowned 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 modifying 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 needs a functor computing the Jacobian. It can be computed by 79 * hand, using auto-differentiation (see \ref AutoDiff_Module), or using numerical 80 * differences (see \ref NumericalDiff_Module). For instance: 81 *\code 82 * MyFunc func; 83 * NumericalDiff<MyFunc> func_with_num_diff(func); 84 * LevenbergMarquardt<NumericalDiff<MyFunc> > lm(func_with_num_diff); 85 * \endcode 86 * For HybridNonLinearSolver, the method solveNumericalDiff() does the above wrapping for 87 * you. 88 * 89 * The methods LevenbergMarquardt.lmder1()/lmdif1()/lmstr1() and 90 * HybridNonLinearSolver.hybrj1()/hybrd1() are specific methods from the original 91 * minpack package that you probably should NOT use until you are porting a code that 92 * was previously using minpack. They just define a 'simple' API with default values 93 * for some parameters. 94 * 95 * All algorithms are provided using two APIs : 96 * - one where the user inits the algorithm, and uses '*OneStep()' as much as he wants : 97 * this way the caller have control over the steps 98 * - one where the user just calls a method (optimize() or solve()) which will 99 * handle the loop: init + loop until a stop condition is met. Those are provided for 100 * convenience. 101 * 102 * As an example, the method LevenbergMarquardt::minimize() is 103 * implemented as follow: 104 * \code 105 * Status LevenbergMarquardt<FunctorType,Scalar>::minimize(FVectorType &x, const int mode) 106 * { 107 * Status status = minimizeInit(x, mode); 108 * do { 109 * status = minimizeOneStep(x, mode); 110 * } while (status==Running); 111 * return status; 112 * } 113 * \endcode 114 * 115 * \section examples Examples 116 * 117 * The easiest way to understand how to use this module is by looking at the many examples in the file 118 * unsupported/test/NonLinearOptimization.cpp. 119 */ 120 121#ifndef EIGEN_PARSED_BY_DOXYGEN 122 123#include "src/NonLinearOptimization/qrsolv.h" 124#include "src/NonLinearOptimization/r1updt.h" 125#include "src/NonLinearOptimization/r1mpyq.h" 126#include "src/NonLinearOptimization/rwupdt.h" 127#include "src/NonLinearOptimization/fdjac1.h" 128#include "src/NonLinearOptimization/lmpar.h" 129#include "src/NonLinearOptimization/dogleg.h" 130#include "src/NonLinearOptimization/covar.h" 131 132#include "src/NonLinearOptimization/chkder.h" 133 134#endif 135 136#include "src/NonLinearOptimization/HybridNonLinearSolver.h" 137#include "src/NonLinearOptimization/LevenbergMarquardt.h" 138 139 140#endif // EIGEN_NONLINEAROPTIMIZATION_MODULE 141