NonLinearOptimization 5.8 KB

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