internal/ceres/trust_region_minimizer.h

   1 // Ceres Solver - A fast non-linear least squares minimizer
   2 // Copyright 2016 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_TRUST_REGION_MINIMIZER_H_
  32 #define CERES_INTERNAL_TRUST_REGION_MINIMIZER_H_
  33
  34 #include "ceres/internal/eigen.h"
  35 #include "ceres/internal/scoped_ptr.h"
  36 #include "ceres/minimizer.h"
  37 #include "ceres/solver.h"
  38 #include "ceres/sparse_matrix.h"
  39 #include "ceres/trust_region_step_evaluator.h"
  40 #include "ceres/trust_region_strategy.h"
  41 #include "ceres/types.h"
  42
  43 namespace ceres {
  44 namespace internal {
  45
  46 // Generic trust region minimization algorithm.
  47 //
  48 // For example usage, see SolverImpl::Minimize.
  49 class TrustRegionMinimizer : public Minimizer {
  50  public:
  51   ~TrustRegionMinimizer();
  52
  53   // This method is not thread safe.
  54   virtual void Minimize(const Minimizer::Options& options,
  55                         double* parameters,
  56                         Solver::Summary* solver_summary);
  57
  58  private:
  59   void Init(const Minimizer::Options& options,
  60             double* parameters,
  61             Solver::Summary* solver_summary);
  62   bool IterationZero();
  63   bool FinalizeIterationAndCheckIfMinimizerCanContinue();
  64   bool ComputeTrustRegionStep();
  65
  66   bool EvaluateGradientAndJacobian();
  67   void ComputeCandidatePointAndEvaluateCost();
  68
  69   void DoLineSearch(const Vector& x,
  70                     const Vector& gradient,
  71                     const double cost,
  72                     Vector* delta);
  73   void DoInnerIterationsIfNeeded();
  74
  75   bool ParameterToleranceReached();
  76   bool FunctionToleranceReached();
  77   bool GradientToleranceReached();
  78   bool MaxSolverTimeReached();
  79   bool MaxSolverIterationsReached();
  80   bool MinTrustRegionRadiusReached();
  81
  82   bool IsStepSuccessful();
  83   void HandleUnsuccessfulStep();
  84   bool HandleSuccessfulStep();
  85   bool HandleInvalidStep();
  86
  87   Minimizer::Options options_;
  88
  89   // These pointers are shortcuts to objects passed to the
  90   // TrustRegionMinimizer. The TrustRegionMinimizer does not own them.
  91   double* parameters_;
  92   Solver::Summary* solver_summary_;
  93   Evaluator* evaluator_;
  94   SparseMatrix* jacobian_;
  95   TrustRegionStrategy* strategy_;
  96
  97   scoped_ptr<TrustRegionStepEvaluator> step_evaluator_;
  98
  99   bool is_not_silent_;
 100   bool inner_iterations_are_enabled_;
 101   bool inner_iterations_were_useful_;
 102
 103   // Summary of the current iteration.
 104   IterationSummary iteration_summary_;
 105
 106   // Dimensionality of the problem in the ambient space.
 107   int num_parameters_;
 108   // Dimensionality of the problem in the tangent space. This is the
 109   // number of columns in the Jacobian.
 110   int num_effective_parameters_;
 111   // Length of the residual vector, also the number of rows in the Jacobian.
 112   int num_residuals_;
 113
 114   // Current point.
 115   Vector x_;
 116   // Residuals at x_;
 117   Vector residuals_;
 118   // Gradient at x_.
 119   Vector gradient_;
 120   // Solution computed by the inner iterations.
 121   Vector inner_iteration_x_;
 122   // model_residuals = J * trust_region_step
 123   Vector model_residuals_;
 124   Vector negative_gradient_;
 125   // projected_gradient_step = Plus(x, -gradient), an intermediate
 126   // quantity used to compute the projected gradient norm.
 127   Vector projected_gradient_step_;
 128   // The step computed by the trust region strategy. If Jacobi scaling
 129   // is enabled, this is a vector in the scaled space.
 130   Vector trust_region_step_;
 131   // The current proposal for how far the trust region algorithm
 132   // thinks we should move. In the most basic case, it is just the
 133   // trust_region_step_ with the Jacobi scaling undone. If bounds
 134   // constraints are present, then it is the result of the projected
 135   // line search.
 136   Vector delta_;
 137   // candidate_x  = Plus(x, delta)
 138   Vector candidate_x_;
 139   // Scaling vector to scale the columns of the Jacobian.
 140   Vector jacobian_scaling_;
 141
 142   // Euclidean norm of x_.
 143   double x_norm_;
 144   // Cost at x_.
 145   double x_cost_;
 146   // Minimum cost encountered up till now.
 147   double minimum_cost_;
 148   // How much did the trust region strategy reduce the cost of the
 149   // linearized Gauss-Newton model.
 150   double model_cost_change_;
 151   // Cost at candidate_x_.
 152   double candidate_cost_;
 153
 154   // Time at which the minimizer was started.
 155   double start_time_in_secs_;
 156   // Time at which the current iteration was started.
 157   double iteration_start_time_in_secs_;
 158   // Number of consecutive steps where the minimizer loop computed a
 159   // numerically invalid step.
 160   int num_consecutive_invalid_steps_;
 161 };
 162
 163 }  // namespace internal
 164 }  // namespace ceres
 165
 166 #endif  // CERES_INTERNAL_TRUST_REGION_MINIMIZER_H_