internal/ceres/gradient_problem_solver.cc

   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 #include "ceres/gradient_problem_solver.h"
  32
  33 #include "ceres/callbacks.h"
  34 #include "ceres/gradient_problem.h"
  35 #include "ceres/gradient_problem_evaluator.h"
  36 #include "ceres/internal/eigen.h"
  37 #include "ceres/internal/port.h"
  38 #include "ceres/map_util.h"
  39 #include "ceres/minimizer.h"
  40 #include "ceres/solver.h"
  41 #include "ceres/solver_utils.h"
  42 #include "ceres/stringprintf.h"
  43 #include "ceres/types.h"
  44 #include "ceres/wall_time.h"
  45
  46 namespace ceres {
  47 using internal::StringPrintf;
  48 using internal::StringAppendF;
  49 using std::string;
  50
  51 namespace {
  52
  53 Solver::Options GradientProblemSolverOptionsToSolverOptions(
  54     const GradientProblemSolver::Options& options) {
  55 #define COPY_OPTION(x) solver_options.x = options.x
  56
  57   Solver::Options solver_options;
  58   solver_options.minimizer_type = LINE_SEARCH;
  59   COPY_OPTION(line_search_direction_type);
  60   COPY_OPTION(line_search_type);
  61   COPY_OPTION(nonlinear_conjugate_gradient_type);
  62   COPY_OPTION(max_lbfgs_rank);
  63   COPY_OPTION(use_approximate_eigenvalue_bfgs_scaling);
  64   COPY_OPTION(line_search_interpolation_type);
  65   COPY_OPTION(min_line_search_step_size);
  66   COPY_OPTION(line_search_sufficient_function_decrease);
  67   COPY_OPTION(max_line_search_step_contraction);
  68   COPY_OPTION(min_line_search_step_contraction);
  69   COPY_OPTION(max_num_line_search_step_size_iterations);
  70   COPY_OPTION(max_num_line_search_direction_restarts);
  71   COPY_OPTION(line_search_sufficient_curvature_decrease);
  72   COPY_OPTION(max_line_search_step_expansion);
  73   COPY_OPTION(max_num_iterations);
  74   COPY_OPTION(max_solver_time_in_seconds);
  75   COPY_OPTION(parameter_tolerance);
  76   COPY_OPTION(function_tolerance);
  77   COPY_OPTION(gradient_tolerance);
  78   COPY_OPTION(logging_type);
  79   COPY_OPTION(minimizer_progress_to_stdout);
  80   COPY_OPTION(callbacks);
  81   return solver_options;
  82 #undef COPY_OPTION
  83 }
  84
  85
  86 }  // namespace
  87
  88 bool GradientProblemSolver::Options::IsValid(std::string* error) const {
  89   const Solver::Options solver_options =
  90       GradientProblemSolverOptionsToSolverOptions(*this);
  91   return solver_options.IsValid(error);
  92 }
  93
  94 GradientProblemSolver::~GradientProblemSolver() {
  95 }
  96
  97 void GradientProblemSolver::Solve(const GradientProblemSolver::Options& options,
  98                                   const GradientProblem& problem,
  99                                   double* parameters_ptr,
 100                                   GradientProblemSolver::Summary* summary) {
 101   using internal::scoped_ptr;
 102   using internal::WallTimeInSeconds;
 103   using internal::Minimizer;
 104   using internal::GradientProblemEvaluator;
 105   using internal::LoggingCallback;
 106   using internal::SetSummaryFinalCost;
 107
 108   double start_time = WallTimeInSeconds();
 109
 110   *CHECK_NOTNULL(summary) = Summary();
 111   summary->num_parameters                    = problem.NumParameters();
 112   summary->num_local_parameters              = problem.NumLocalParameters();
 113   summary->line_search_direction_type        = options.line_search_direction_type;         //  NOLINT
 114   summary->line_search_interpolation_type    = options.line_search_interpolation_type;     //  NOLINT
 115   summary->line_search_type                  = options.line_search_type;
 116   summary->max_lbfgs_rank                    = options.max_lbfgs_rank;
 117   summary->nonlinear_conjugate_gradient_type = options.nonlinear_conjugate_gradient_type;  //  NOLINT
 118
 119   // Check validity
 120   if (!options.IsValid(&summary->message)) {
 121     LOG(ERROR) << "Terminating: " << summary->message;
 122     return;
 123   }
 124
 125   // TODO(sameeragarwal): This is a bit convoluted, we should be able
 126   // to convert to minimizer options directly, but this will do for
 127   // now.
 128   Minimizer::Options minimizer_options =
 129       Minimizer::Options(GradientProblemSolverOptionsToSolverOptions(options));
 130   minimizer_options.evaluator.reset(new GradientProblemEvaluator(problem));
 131
 132   scoped_ptr<IterationCallback> logging_callback;
 133   if (options.logging_type != SILENT) {
 134     logging_callback.reset(
 135         new LoggingCallback(LINE_SEARCH, options.minimizer_progress_to_stdout));
 136     minimizer_options.callbacks.insert(minimizer_options.callbacks.begin(),
 137                                        logging_callback.get());
 138   }
 139
 140   scoped_ptr<Minimizer> minimizer(Minimizer::Create(LINE_SEARCH));
 141   Vector solution(problem.NumParameters());
 142   VectorRef parameters(parameters_ptr, problem.NumParameters());
 143   solution = parameters;
 144
 145   Solver::Summary solver_summary;
 146   solver_summary.fixed_cost = 0.0;
 147   solver_summary.preprocessor_time_in_seconds = 0.0;
 148   solver_summary.postprocessor_time_in_seconds = 0.0;
 149   solver_summary.line_search_polynomial_minimization_time_in_seconds = 0.0;
 150
 151   minimizer->Minimize(minimizer_options, solution.data(), &solver_summary);
 152
 153   summary->termination_type = solver_summary.termination_type;
 154   summary->message          = solver_summary.message;
 155   summary->initial_cost     = solver_summary.initial_cost;
 156   summary->final_cost       = solver_summary.final_cost;
 157   summary->iterations       = solver_summary.iterations;
 158   summary->line_search_polynomial_minimization_time_in_seconds =
 159       solver_summary.line_search_polynomial_minimization_time_in_seconds;
 160
 161   if (summary->IsSolutionUsable()) {
 162     parameters = solution;
 163     SetSummaryFinalCost(summary);
 164   }
 165
 166   const std::map<string, double>& evaluator_time_statistics =
 167        minimizer_options.evaluator->TimeStatistics();
 168   summary->cost_evaluation_time_in_seconds =
 169       FindWithDefault(evaluator_time_statistics, "Evaluator::Residual", 0.0);
 170   summary->gradient_evaluation_time_in_seconds =
 171       FindWithDefault(evaluator_time_statistics, "Evaluator::Jacobian", 0.0);
 172   const std::map<string, int>& evaluator_call_statistics =
 173        minimizer_options.evaluator->CallStatistics();
 174   summary->num_cost_evaluations =
 175       FindWithDefault(evaluator_call_statistics, "Evaluator::Residual", 0);
 176   summary->num_gradient_evaluations =
 177       FindWithDefault(evaluator_call_statistics, "Evaluator::Jacobian", 0);
 178   summary->total_time_in_seconds = WallTimeInSeconds() - start_time;
 179 }
 180
 181 // Invalid values for most fields, to ensure that we are not
 182 // accidentally reporting default values.
 183 GradientProblemSolver::Summary::Summary()
 184     : termination_type(FAILURE),
 185       message("ceres::GradientProblemSolve was not called."),
 186       initial_cost(-1.0),
 187       final_cost(-1.0),
 188       total_time_in_seconds(-1.0),
 189       cost_evaluation_time_in_seconds(-1.0),
 190       gradient_evaluation_time_in_seconds(-1.0),
 191       line_search_polynomial_minimization_time_in_seconds(-1.0),
 192       num_parameters(-1),
 193       num_local_parameters(-1),
 194       line_search_direction_type(LBFGS),
 195       line_search_type(ARMIJO),
 196       line_search_interpolation_type(BISECTION),
 197       nonlinear_conjugate_gradient_type(FLETCHER_REEVES),
 198       max_lbfgs_rank(-1) {
 199 }
 200
 201 bool GradientProblemSolver::Summary::IsSolutionUsable() const {
 202   return internal::IsSolutionUsable(*this);
 203 }
 204
 205 string GradientProblemSolver::Summary::BriefReport() const {
 206   return StringPrintf("Ceres GradientProblemSolver Report: "
 207                       "Iterations: %d, "
 208                       "Initial cost: %e, "
 209                       "Final cost: %e, "
 210                       "Termination: %s",
 211                       static_cast<int>(iterations.size()),
 212                       initial_cost,
 213                       final_cost,
 214                       TerminationTypeToString(termination_type));
 215 }
 216
 217 string GradientProblemSolver::Summary::FullReport() const {
 218   using internal::VersionString;
 219
 220   string report = string("\nSolver Summary (v " + VersionString() + ")\n\n");
 221
 222   StringAppendF(&report, "Parameters          % 25d\n", num_parameters);
 223   if (num_local_parameters != num_parameters) {
 224     StringAppendF(&report, "Local parameters    % 25d\n",
 225                   num_local_parameters);
 226   }
 227
 228   string line_search_direction_string;
 229   if (line_search_direction_type == LBFGS) {
 230     line_search_direction_string = StringPrintf("LBFGS (%d)", max_lbfgs_rank);
 231   } else if (line_search_direction_type == NONLINEAR_CONJUGATE_GRADIENT) {
 232     line_search_direction_string =
 233         NonlinearConjugateGradientTypeToString(
 234             nonlinear_conjugate_gradient_type);
 235   } else {
 236     line_search_direction_string =
 237         LineSearchDirectionTypeToString(line_search_direction_type);
 238   }
 239
 240   StringAppendF(&report, "Line search direction     %19s\n",
 241                 line_search_direction_string.c_str());
 242
 243   const string line_search_type_string =
 244       StringPrintf("%s %s",
 245                    LineSearchInterpolationTypeToString(
 246                        line_search_interpolation_type),
 247                    LineSearchTypeToString(line_search_type));
 248   StringAppendF(&report, "Line search type          %19s\n",
 249                 line_search_type_string.c_str());
 250   StringAppendF(&report, "\n");
 251
 252   StringAppendF(&report, "\nCost:\n");
 253   StringAppendF(&report, "Initial        % 30e\n", initial_cost);
 254   if (termination_type != FAILURE &&
 255       termination_type != USER_FAILURE) {
 256     StringAppendF(&report, "Final          % 30e\n", final_cost);
 257     StringAppendF(&report, "Change         % 30e\n",
 258                   initial_cost - final_cost);
 259   }
 260
 261   StringAppendF(&report, "\nMinimizer iterations         % 16d\n",
 262                 static_cast<int>(iterations.size()));
 263
 264   StringAppendF(&report, "\nTime (in seconds):\n");
 265   StringAppendF(&report, "\n  Cost evaluation     %23.4f (%d)\n",
 266                 cost_evaluation_time_in_seconds,
 267                 num_cost_evaluations);
 268   StringAppendF(&report, "  Gradient evaluation %23.4f (%d)\n",
 269                 gradient_evaluation_time_in_seconds,
 270                 num_gradient_evaluations);
 271   StringAppendF(&report, "  Polynomial minimization   %17.4f\n",
 272                 line_search_polynomial_minimization_time_in_seconds);
 273   StringAppendF(&report, "Total               %25.4f\n\n",
 274                 total_time_in_seconds);
 275
 276   StringAppendF(&report, "Termination:        %25s (%s)\n",
 277                 TerminationTypeToString(termination_type), message.c_str());
 278   return report;
 279 }
 280
 281 void Solve(const GradientProblemSolver::Options& options,
 282            const GradientProblem& problem,
 283            double* parameters,
 284            GradientProblemSolver::Summary* summary) {
 285   GradientProblemSolver solver;
 286   solver.Solve(options, problem, parameters, summary);
 287 }
 288
 289 }  // namespace ceres