internal/ceres/minimizer.h

   1 // Ceres Solver - A fast non-linear least squares minimizer
   2 // Copyright 2015 Google Inc. All rights reserved.
   3 // http://ceres-solver.org/
   4 //
   5 // Redistribution and use in source and binary forms, with or without
   6 // modification, are permitted provided that the following conditions are met:
   7 //
   8 // * Redistributions of source code must retain the above copyright notice,
   9 //   this list of conditions and the following disclaimer.
  10 // * Redistributions in binary form must reproduce the above copyright notice,
  11 //   this list of conditions and the following disclaimer in the documentation
  12 //   and/or other materials provided with the distribution.
  13 // * Neither the name of Google Inc. nor the names of its contributors may be
  14 //   used to endorse or promote products derived from this software without
  15 //   specific prior written permission.
  16 //
  17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  21 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  22 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  23 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  24 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  25 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  26 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  27 // POSSIBILITY OF SUCH DAMAGE.
  28 //
  29 // Author: sameeragarwal@google.com (Sameer Agarwal)
  30
  31 #ifndef CERES_INTERNAL_MINIMIZER_H_
  32 #define CERES_INTERNAL_MINIMIZER_H_
  33
  34 #include <string>
  35 #include <vector>
  36 #include "ceres/internal/port.h"
  37 #include "ceres/iteration_callback.h"
  38 #include "ceres/solver.h"
  39
  40 namespace ceres {
  41 namespace internal {
  42
  43 class Evaluator;
  44 class SparseMatrix;
  45 class TrustRegionStrategy;
  46 class CoordinateDescentMinimizer;
  47 class LinearSolver;
  48
  49 // Interface for non-linear least squares solvers.
  50 class Minimizer {
  51  public:
  52   // Options struct to control the behaviour of the Minimizer. Please
  53   // see solver.h for detailed information about the meaning and
  54   // default values of each of these parameters.
  55   struct Options {
  56     Options() {
  57       Init(Solver::Options());
  58     }
  59
  60     explicit Options(const Solver::Options& options) {
  61       Init(options);
  62     }
  63
  64     void Init(const Solver::Options& options) {
  65       num_threads = options.num_threads;
  66       max_num_iterations = options.max_num_iterations;
  67       max_solver_time_in_seconds = options.max_solver_time_in_seconds;
  68       max_step_solver_retries = 5;
  69       gradient_tolerance = options.gradient_tolerance;
  70       parameter_tolerance = options.parameter_tolerance;
  71       function_tolerance = options.function_tolerance;
  72       min_relative_decrease = options.min_relative_decrease;
  73       eta = options.eta;
  74       jacobi_scaling = options.jacobi_scaling;
  75       use_nonmonotonic_steps = options.use_nonmonotonic_steps;
  76       max_consecutive_nonmonotonic_steps =
  77           options.max_consecutive_nonmonotonic_steps;
  78       trust_region_problem_dump_directory =
  79           options.trust_region_problem_dump_directory;
  80       trust_region_minimizer_iterations_to_dump =
  81           options.trust_region_minimizer_iterations_to_dump;
  82       trust_region_problem_dump_format_type =
  83           options.trust_region_problem_dump_format_type;
  84       max_num_consecutive_invalid_steps =
  85           options.max_num_consecutive_invalid_steps;
  86       min_trust_region_radius = options.min_trust_region_radius;
  87       line_search_direction_type = options.line_search_direction_type;
  88       line_search_type = options.line_search_type;
  89       nonlinear_conjugate_gradient_type =
  90           options.nonlinear_conjugate_gradient_type;
  91       max_lbfgs_rank = options.max_lbfgs_rank;
  92       use_approximate_eigenvalue_bfgs_scaling =
  93           options.use_approximate_eigenvalue_bfgs_scaling;
  94       line_search_interpolation_type =
  95           options.line_search_interpolation_type;
  96       min_line_search_step_size = options.min_line_search_step_size;
  97       line_search_sufficient_function_decrease =
  98           options.line_search_sufficient_function_decrease;
  99       max_line_search_step_contraction =
 100           options.max_line_search_step_contraction;
 101       min_line_search_step_contraction =
 102           options.min_line_search_step_contraction;
 103       max_num_line_search_step_size_iterations =
 104           options.max_num_line_search_step_size_iterations;
 105       max_num_line_search_direction_restarts =
 106           options.max_num_line_search_direction_restarts;
 107       line_search_sufficient_curvature_decrease =
 108           options.line_search_sufficient_curvature_decrease;
 109       max_line_search_step_expansion =
 110           options.max_line_search_step_expansion;
 111       inner_iteration_tolerance = options.inner_iteration_tolerance;
 112       is_silent = (options.logging_type == SILENT);
 113       is_constrained = false;
 114       callbacks = options.callbacks;
 115     }
 116
 117     int max_num_iterations;
 118     double max_solver_time_in_seconds;
 119     int num_threads;
 120
 121     // Number of times the linear solver should be retried in case of
 122     // numerical failure. The retries are done by exponentially scaling up
 123     // mu at each retry. This leads to stronger and stronger
 124     // regularization making the linear least squares problem better
 125     // conditioned at each retry.
 126     int max_step_solver_retries;
 127     double gradient_tolerance;
 128     double parameter_tolerance;
 129     double function_tolerance;
 130     double min_relative_decrease;
 131     double eta;
 132     bool jacobi_scaling;
 133     bool use_nonmonotonic_steps;
 134     int max_consecutive_nonmonotonic_steps;
 135     std::vector<int> trust_region_minimizer_iterations_to_dump;
 136     DumpFormatType trust_region_problem_dump_format_type;
 137     std::string trust_region_problem_dump_directory;
 138     int max_num_consecutive_invalid_steps;
 139     double min_trust_region_radius;
 140     LineSearchDirectionType line_search_direction_type;
 141     LineSearchType line_search_type;
 142     NonlinearConjugateGradientType nonlinear_conjugate_gradient_type;
 143     int max_lbfgs_rank;
 144     bool use_approximate_eigenvalue_bfgs_scaling;
 145     LineSearchInterpolationType line_search_interpolation_type;
 146     double min_line_search_step_size;
 147     double line_search_sufficient_function_decrease;
 148     double max_line_search_step_contraction;
 149     double min_line_search_step_contraction;
 150     int max_num_line_search_step_size_iterations;
 151     int max_num_line_search_direction_restarts;
 152     double line_search_sufficient_curvature_decrease;
 153     double max_line_search_step_expansion;
 154     double inner_iteration_tolerance;
 155
 156     // If true, then all logging is disabled.
 157     bool is_silent;
 158
 159     // Use a bounds constrained optimization algorithm.
 160     bool is_constrained;
 161
 162     // List of callbacks that are executed by the Minimizer at the end
 163     // of each iteration.
 164     //
 165     // The Options struct does not own these pointers.
 166     std::vector<IterationCallback*> callbacks;
 167
 168     // Object responsible for evaluating the cost, residuals and
 169     // Jacobian matrix.
 170     shared_ptr<Evaluator> evaluator;
 171
 172     // Object responsible for actually computing the trust region
 173     // step, and sizing the trust region radius.
 174     shared_ptr<TrustRegionStrategy> trust_region_strategy;
 175
 176     // Object holding the Jacobian matrix. It is assumed that the
 177     // sparsity structure of the matrix has already been initialized
 178     // and will remain constant for the life time of the
 179     // optimization.
 180     shared_ptr<SparseMatrix> jacobian;
 181
 182     shared_ptr<CoordinateDescentMinimizer> inner_iteration_minimizer;
 183   };
 184
 185   static Minimizer* Create(MinimizerType minimizer_type);
 186   static bool RunCallbacks(const Options& options,
 187                            const IterationSummary& iteration_summary,
 188                            Solver::Summary* summary);
 189
 190   virtual ~Minimizer();
 191   // Note: The minimizer is expected to update the state of the
 192   // parameters array every iteration. This is required for the
 193   // StateUpdatingCallback to work.
 194   virtual void Minimize(const Options& options,
 195                         double* parameters,
 196                         Solver::Summary* summary) = 0;
 197 };
 198
 199 }  // namespace internal
 200 }  // namespace ceres
 201
 202 #endif  // CERES_INTERNAL_MINIMIZER_H_