1 // Ceres Solver - A fast non-linear least squares minimizer 2 // Copyright 2012 Google Inc. All rights reserved. 3 // http://code.google.com/p/ceres-solver/ 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 (at) google.com (Sameer Agarwal) 30 31 #ifndef CERES_INTERNAL_TRUST_REGION_STRATEGY_H_ 32 #define CERES_INTERNAL_TRUST_REGION_STRATEGY_H_ 33 34 #include "ceres/types.h" 35 36 namespace ceres { 37 namespace internal { 38 39 class LinearSolver; 40 class SparseMatrix; 41 42 // Interface for classes implementing various trust region strategies 43 // for nonlinear least squares problems. 44 // 45 // The object is expected to maintain and update a trust region 46 // radius, which it then uses to solve for the trust region step using 47 // the jacobian matrix and residual vector. 48 // 49 // Here the term trust region radius is used loosely, as the strategy 50 // is free to treat it as guidance and violate it as need be. e.g., 51 // the LevenbergMarquardtStrategy uses the inverse of the trust region 52 // radius to scale the damping term, which controls the step size, but 53 // does not set a hard limit on its size. 54 class TrustRegionStrategy { 55 public: 56 struct Options { 57 Options() 58 : trust_region_strategy_type(LEVENBERG_MARQUARDT), 59 initial_radius(1e4), 60 max_radius(1e32), 61 lm_min_diagonal(1e-6), 62 lm_max_diagonal(1e32), 63 dogleg_type(TRADITIONAL_DOGLEG) { 64 } 65 66 TrustRegionStrategyType trust_region_strategy_type; 67 // Linear solver used for actually solving the trust region step. 68 LinearSolver* linear_solver; 69 double initial_radius; 70 double max_radius; 71 72 // Minimum and maximum values of the diagonal damping matrix used 73 // by LevenbergMarquardtStrategy. The DoglegStrategy also uses 74 // these bounds to construct a regularizing diagonal to ensure 75 // that the Gauss-Newton step computation is of full rank. 76 double lm_min_diagonal; 77 double lm_max_diagonal; 78 79 // Further specify which dogleg method to use 80 DoglegType dogleg_type; 81 }; 82 83 // Per solve options. 84 struct PerSolveOptions { 85 // Forcing sequence for inexact solves. 86 double eta; 87 }; 88 89 struct Summary { 90 Summary() 91 : residual_norm(0.0), 92 num_iterations(-1), 93 termination_type(FAILURE) { 94 } 95 96 // If the trust region problem is, 97 // 98 // 1/2 x'Ax + b'x + c, 99 // 100 // then 101 // 102 // residual_norm = |Ax -b| 103 double residual_norm; 104 105 // Number of iterations used by the linear solver. If a linear 106 // solver was not called (e.g., DogLegStrategy after an 107 // unsuccessful step), then this would be zero. 108 int num_iterations; 109 110 // Status of the linear solver used to solve the Newton system. 111 LinearSolverTerminationType termination_type; 112 }; 113 114 virtual ~TrustRegionStrategy(); 115 116 // Use the current radius to solve for the trust region step. 117 virtual Summary ComputeStep(const PerSolveOptions& per_solve_options, 118 SparseMatrix* jacobian, 119 const double* residuals, 120 double* step) = 0; 121 122 // Inform the strategy that the current step has been accepted, and 123 // that the ratio of the decrease in the non-linear objective to the 124 // decrease in the trust region model is step_quality. 125 virtual void StepAccepted(double step_quality) = 0; 126 127 // Inform the strategy that the current step has been rejected, and 128 // that the ratio of the decrease in the non-linear objective to the 129 // decrease in the trust region model is step_quality. 130 virtual void StepRejected(double step_quality) = 0; 131 132 // Inform the strategy that the current step has been rejected 133 // because it was found to be numerically invalid. 134 // StepRejected/StepAccepted will not be called for this step, and 135 // the strategy is free to do what it wants with this information. 136 virtual void StepIsInvalid() = 0; 137 138 // Current trust region radius. 139 virtual double Radius() const = 0; 140 141 // Factory. 142 static TrustRegionStrategy* Create(const Options& options); 143 }; 144 145 } // namespace internal 146 } // namespace ceres 147 148 #endif // CERES_INTERNAL_TRUST_REGION_STRATEGY_H_ 149
