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