1 // This is core/vnl/vnl_nonlinear_minimizer.h
2 #ifndef vnl_nonlinear_minimizer_h_
3 #define vnl_nonlinear_minimizer_h_
4 //:
5 // \file
6 // \brief  Base class for nonlinear optimization
7 // \author Andrew W. Fitzgibbon, Oxford RRG
8 // \date   22 Aug 1999
9 //
10 // \verbatim
11 //  Modifications
12 //   22 Mar.2001 - dac - added binary io and tidied documentation
13 //      Feb.2002 - Peter Vanroose - brief doxygen comment placed on single line
14 // \endverbatim
15 
16 #include <string>
17 #ifdef _MSC_VER
18 #  include <vcl_msvc_warnings.h>
19 #endif
20 #include <vnl/vnl_matrix.h>
21 #include "vnl/vnl_export.h"
22 
23 //: vnl_nonlinear_minimizer is a base class for nonlinear optimization.
24 // It defines a few common abilities such as get_num_evaluations.
25 // Known derived classes are:
26 // -  vnl_levenberg_marquardt
27 // -  vnl_lbfgs
28 // -  vnl_conjugate_gradient
29 // -  vnl_brent
30 // -  vnl_powell
31 class VNL_EXPORT vnl_nonlinear_minimizer
32 {
33  public:
34   vnl_nonlinear_minimizer();
35 
36   virtual ~vnl_nonlinear_minimizer();
37 
38 
39   //: Set the convergence tolerance on F (sum of squared residuals).
40   // When the differences in successive RMS errors is less than this, the
41   // routine terminates.  So this is effectively the desired precision of your
42   // minimization.  Setting it too low wastes time, too high might cause early
43   // convergence.  The default of 1e-9 is on the safe side, but if speed is an
44   // issue, you can try raising it.
set_f_tolerance(double v)45   void set_f_tolerance(double v) { ftol = v; }
get_f_tolerance()46   double get_f_tolerance() const { return ftol; }
47 
48   //: Set the convergence tolerance on X.
49   //  When the length of the steps taken in X are about this long, the routine
50   // terminates.  The default is 1e-8, which should work for many problems,
51   // but if you can get away with 1e-4, say, minimizations will be much quicker.
set_x_tolerance(double v)52   void set_x_tolerance(double v) {
53     xtol = v;
54     epsfcn = xtol * 0.001;
55   }
get_x_tolerance()56   double get_x_tolerance() const { return xtol; }
57 
58   //: Set the convergence tolerance on Grad(F)' * F.
set_g_tolerance(double v)59   void set_g_tolerance(double v) { gtol = v; }
get_g_tolerance()60   double get_g_tolerance() const { return gtol; }
61 
62   //: Set the termination maximum number of iterations.
set_max_function_evals(int v)63   void set_max_function_evals(int v) { maxfev = v; }
get_max_function_evals()64   int get_max_function_evals() const { return maxfev; }
65 
66   //: Set the step length for FD Jacobian.
67   // Be aware that set_x_tolerance will reset this to xtol * 0.001.
68   // The default is 1e-11.
set_epsilon_function(double v)69   void set_epsilon_function(double v) { epsfcn = v; }
get_epsilon_function()70   double get_epsilon_function() const { return epsfcn; }
71 
72   //: Turn on per-iteration printouts.
set_trace(bool on)73   void set_trace(bool on) { trace = on; }
get_trace()74   bool get_trace() const { return trace; }
75 
76   //: Set verbose flag
set_verbose(bool verb)77   void set_verbose(bool verb) { verbose_ = verb; }
get_verbose()78   bool get_verbose() const { return verbose_; }
79 
80   //: Set check_derivatives flag.  Negative values may mean fewer checks.
set_check_derivatives(int cd)81   void set_check_derivatives(int cd) { check_derivatives_ = cd; }
get_check_derivatives()82   int get_check_derivatives() const { return check_derivatives_; }
83 
84   //: Return the error of the function when it was evaluated at the start point of the last minimization.
85   // For minimizers driven by a vnl_least_squares_function (Levenberg-Marquardt)
86   // this is usually the RMS error.
87   // For those driven by a vnl_cost_function (CG, LBFGS, Amoeba) it is simply the
88   // value of the vnl_cost_function at the start (usually the sum of squared residuals).
get_start_error()89   double get_start_error() const { return start_error_; }
90 
91   //:Return the best error that was achieved by the last minimization, corresponding to the returned x.
get_end_error()92   double get_end_error() const { return end_error_; }
93 
94   //:Return the total number of times the function was evaluated by the last minimization.
get_num_evaluations()95   int get_num_evaluations() const { return num_evaluations_; }
96 
97   //:Return the number of {\em iterations} in the last minimization.
98   // Each iteration may have comprised several function evaluations.
get_num_iterations()99   int get_num_iterations() const { return num_iterations_; }
100 
101   //:Some generic return codes that apply to all minimizers.
102   enum ReturnCodes {
103     ERROR_FAILURE               =-1,
104     ERROR_DODGY_INPUT           = 0,
105     CONVERGED_FTOL              = 1,
106     CONVERGED_XTOL              = 2,
107     CONVERGED_XFTOL             = 3,
108     CONVERGED_GTOL              = 4,
109     FAILED_TOO_MANY_ITERATIONS  = 5,
110     TOO_MANY_ITERATIONS         = FAILED_TOO_MANY_ITERATIONS,         // for backward-compatibility
111     FAILED_FTOL_TOO_SMALL       = 6,
112     FAILED_XTOL_TOO_SMALL       = 7,
113     FAILED_GTOL_TOO_SMALL       = 8,
114     FAILED_USER_REQUEST         = 9
115   };
116 
117   //:Whether the error reduced in the last minimization
obj_value_reduced()118   bool obj_value_reduced() { return failure_code_ != ERROR_FAILURE && failure_code_ != ERROR_DODGY_INPUT && end_error_ < start_error_; }
119 
120   //:Return the covariance of the estimate at the end.
121   virtual vnl_matrix<double> const& get_covariance();
122 
123   //: Return the name of the class.
124   //  Used by polymorphic IO
125   virtual std::string is_a() const;
126 
127   //: Return true if the name of the class matches the argument.
128   //  Used by polymorphic IO
129   virtual bool is_class(std::string const& s) const;
130 
131   //:Return the failure code of the last minimization
get_failure_code()132   ReturnCodes get_failure_code() const { return failure_code_; }
133 
134  protected:
135   // Data Members--------------------------------------------------------------
136   // Input variables
137   double xtol;    //!< Termination tolerance on X (solution vector)
138   long   maxfev;  //!< Termination maximum number of iterations
139   double ftol;    //!< Termination tolerance on F (sum of squared residuals)
140   double gtol;    //!< Termination tolerance on Grad(F)' * F = 0
141   double epsfcn;  //!< Step length for FD Jacobian
142 
143   // Output variables
144   unsigned num_iterations_;
145   long    num_evaluations_;
146   double start_error_;
147   double end_error_;
148 
149   bool trace;
150 
151   // Verbose flag.
152   bool verbose_;
153   int check_derivatives_;
154   ReturnCodes failure_code_;
155 
156   void reset();
157 
158   //: Called by derived classes after each function evaluation.
159   void report_eval(double f);
160 
161   //: Called by derived classes after each iteration.
162   //  When true is returned, minimizer should stop with code FAILED_USER_REQUEST.
163   //  Derived classes can redefine this function to make the optimizer stop when a condition is satisfied.
164   virtual bool report_iter();
165 };
166 
167 #endif // vnl_nonlinear_minimizer_h_
168