Add more documentation.
Add documentation to the TrustRegionMinimizer and
TrustRegionStepEvaluator.
Change-Id: I3651e41ff37955a0b7044910403630af1a855071
diff --git a/internal/ceres/trust_region_minimizer.cc b/internal/ceres/trust_region_minimizer.cc
index 8d4407b..35c7c41 100644
--- a/internal/ceres/trust_region_minimizer.cc
+++ b/internal/ceres/trust_region_minimizer.cc
@@ -66,8 +66,8 @@
void TrustRegionMinimizer::Minimize(const Minimizer::Options& options,
double* parameters,
Solver::Summary* solver_summary) {
- start_time_ = WallTimeInSeconds();
- iteration_start_time_ = start_time_;
+ start_time_in_secs_ = WallTimeInSeconds();
+ iteration_start_time_in_secs_ = start_time_in_secs_;
Init(options, parameters, solver_summary);
RETURN_IF_ERROR_AND_LOG(IterationZero());
@@ -81,7 +81,7 @@
: 0));
while (FinalizeIterationAndCheckIfMinimizerCanContinue()) {
- iteration_start_time_ = WallTimeInSeconds();
+ iteration_start_time_in_secs_ = WallTimeInSeconds();
iteration_summary_ = IterationSummary();
iteration_summary_.iteration =
solver_summary->iterations.back().iteration + 1;
@@ -304,9 +304,9 @@
iteration_summary_.trust_region_radius = strategy_->Radius();
iteration_summary_.iteration_time_in_seconds =
- WallTimeInSeconds() - iteration_start_time_;
+ WallTimeInSeconds() - iteration_start_time_in_secs_;
iteration_summary_.cumulative_time_in_seconds =
- WallTimeInSeconds() - start_time_ +
+ WallTimeInSeconds() - start_time_in_secs_ +
solver_summary_->preprocessor_time_in_seconds;
solver_summary_->iterations.push_back(iteration_summary_);
@@ -590,9 +590,12 @@
}
}
+// Check if the maximum amount of time allowed by the user for the
+// solver has been exceeded, and if so return false after updating
+// Solver::Summary::message.
bool TrustRegionMinimizer::MaxSolverTimeReached() {
const double total_solver_time =
- WallTimeInSeconds() - start_time_ +
+ WallTimeInSeconds() - start_time_in_secs_ +
solver_summary_->preprocessor_time_in_seconds;
if (total_solver_time < options_.max_solver_time_in_seconds) {
return false;
@@ -607,6 +610,9 @@
return true;
}
+// Check if the maximum number of iterations allowed by the user for
+// the solver has been exceeded, and if so return false after updating
+// Solver::Summary::message.
bool TrustRegionMinimizer::MaxSolverIterationsReached() {
if (iteration_summary_.iteration < options_.max_num_iterations) {
return false;
@@ -622,6 +628,8 @@
return true;
}
+// Check convergence based on the max norm of the gradient (only for
+// iterations where the step was declared successful).
bool TrustRegionMinimizer::GradientToleranceReached() {
if (!iteration_summary_.step_is_successful ||
iteration_summary_.gradient_max_norm > options_.gradient_tolerance) {
@@ -638,6 +646,7 @@
return true;
}
+// Check convergence based the size of the trust region radius.
bool TrustRegionMinimizer::MinTrustRegionRadiusReached() {
if (iteration_summary_.trust_region_radius >
options_.min_trust_region_radius) {
@@ -751,6 +760,9 @@
options_.min_relative_decrease);
}
+// Declare the step successful, move to candidate_x, update the
+// derivatives and let the trust region strategy and the step
+// evaluator know that the step has been accepted.
bool TrustRegionMinimizer::HandleSuccessfulStep() {
x_ = candidate_x_;
x_norm_ = x_.norm();
@@ -765,6 +777,7 @@
return true;
}
+// Declare the step unsuccessful and inform the trust region strategy.
void TrustRegionMinimizer::HandleUnsuccessfulStep() {
iteration_summary_.step_is_successful = false;
strategy_->StepRejected(iteration_summary_.relative_decrease);
diff --git a/internal/ceres/trust_region_minimizer.h b/internal/ceres/trust_region_minimizer.h
index ac4a6ed..43141da 100644
--- a/internal/ceres/trust_region_minimizer.h
+++ b/internal/ceres/trust_region_minimizer.h
@@ -103,30 +103,60 @@
// Summary of the current iteration.
IterationSummary iteration_summary_;
+ // Dimensionality of the problem in the ambient space.
int num_parameters_;
+ // Dimensionality of the problem in the tangent space. This is the
+ // number of columns in the Jacobian.
int num_effective_parameters_;
+ // Length of the residual vector, also the number of rows in the Jacobian.
int num_residuals_;
- Vector delta_;
+ // Current point.
+ Vector x_;
+ // Residuals at x_;
+ Vector residuals_;
+ // Gradient at x_.
Vector gradient_;
+ // Solution computed by the inner iterations.
Vector inner_iteration_x_;
+ // model_residuals = J * trust_region_step
Vector model_residuals_;
Vector negative_gradient_;
+ // projected_gradient_step = Plus(x, -gradient), an intermediate
+ // quantity used to compute the projected gradient norm.
Vector projected_gradient_step_;
- Vector residuals_;
+ // The step computed by the trust region strategy. If Jacobi scaling
+ // is enabled, this is a vector in the scaled space.
Vector trust_region_step_;
- Vector x_;
+ // The current proposal for how far the trust region algorithm
+ // thinks we should move. In the most basic case, it is just the
+ // trust_region_step_ with the Jacobi scaling undone. If bounds
+ // constraints are present, then it is the result of the projected
+ // line search.
+ Vector delta_;
+ // candidate_x = Plus(x, delta)
Vector candidate_x_;
+ // Scaling vector to scale the columns of the Jacobian.
Vector jacobian_scaling_;
+ // Euclidean norm of x_.
double x_norm_;
+ // Cost at x_.
double x_cost_;
+ // Minimum cost encountered up till now.
double minimum_cost_;
+ // How much did the trust region strategy reduce the cost of the
+ // linearized Gauss-Newton model.
double model_cost_change_;
+ // Cost at candidate_x_.
double candidate_cost_;
- double start_time_;
- double iteration_start_time_;
+ // Time at which the minimizer was started.
+ double start_time_in_secs_;
+ // Time at which the current iteration was started.
+ double iteration_start_time_in_secs_;
+ // Number of consecutive steps where the minimizer loop computed a
+ // numerically invalid step.
int num_consecutive_invalid_steps_;
};
diff --git a/internal/ceres/trust_region_step_evaluator.h b/internal/ceres/trust_region_step_evaluator.h
index 1f14954..06df102 100644
--- a/internal/ceres/trust_region_step_evaluator.h
+++ b/internal/ceres/trust_region_step_evaluator.h
@@ -49,7 +49,7 @@
// increase in the value of the objective function.
//
// This is because allowing for non-decreasing objective function
-// values in a principaled manner allows the algorithm to "jump over
+// values in a principled manner allows the algorithm to "jump over
// boulders" as the method is not restricted to move into narrow
// valleys while preserving its convergence properties.
//
@@ -76,19 +76,43 @@
// }
class TrustRegionStepEvaluator {
public:
+ // initial_cost is as the name implies the cost of the starting
+ // state of the trust region minimizer.
+ //
+ // max_consecutive_nonmonotonic_steps controls the window size used
+ // by the step selection algorithm to accept non-monotonic
+ // steps. Setting this parameter to zero, recovers the classic
+ // montonic descent algorithm.
TrustRegionStepEvaluator(double initial_cost,
int max_consecutive_nonmonotonic_steps);
+
+ // Return the quality of the step given its cost and the decrease in
+ // the cost of the model. model_cost_change has to be positive.
double StepQuality(double cost, double model_cost_change) const;
+
+ // Inform the step evaluator that a step with the given cost and
+ // model_cost_change has been accepted by the trust region
+ // minimizer.
void StepAccepted(double cost, double model_cost_change);
private:
const int max_consecutive_nonmonotonic_steps_;
+ // The minimum cost encountered up till now.
double minimum_cost_;
+ // The current cost of the trust region minimizer as informed by the
+ // last call to StepAccepted.
double current_cost_;
double reference_cost_;
double candidate_cost_;
+ // Accumulated model cost since the last time the reference model
+ // cost was updated, i.e., when a step with cost less than the
+ // current known minimum cost is accepted.
double accumulated_reference_model_cost_change_;
+ // Accumulated model cost since the last time the candidate model
+ // cost was updated, i.e., a non-monotonic step was taken with a
+ // cost that was greater than the current candidate cost.
double accumulated_candidate_model_cost_change_;
+ // Number of steps taken since the last time minimum_cost was updated.
int num_consecutive_nonmonotonic_steps_;
};
