Ceres: Update to the latest actual version
[blender.git] / extern / ceres / 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_