commit 660af905fbefc15c54ae2f82bde452a0254881c6
author Sameer Agarwal <sameeragarwal@google.com> Mon Sep 19 06:25:18 2022 -0700
committer Sameer Agarwal <sameeragarwal@google.com> Mon Sep 19 07:53:27 2022 -0700
tree fd235f1825a41901e9a3fafe3fd3a0825b52a141
parent 4cd257cf4ac8b0b81ab76b5dbac53b2b01de885e

Fix a bug in TrustRegionMinimizer.

The value of x_norm_ was computed and then incorrectly set to -1.
This meant that ParameterToleranceReached was using the incorrect
value till such time as the minimizer made its first successful
step.

This change removes the member variable and just computes
the norm of x inside ParameterToleranceReached.

Fixes https://github.com/ceres-solver/ceres-solver/issues/885

Thanks to Anton Adanasyev for reporting this.

Change-Id: Ib4d52a45c2d925557ce2c5b57de8a9fa37da6c70

internal/ceres/trust_region_minimizer.cc

diff --git a/internal/ceres/trust_region_minimizer.cc b/internal/ceres/trust_region_minimizer.cc
index 6693e6e..60f6b62 100644
--- a/internal/ceres/trust_region_minimizer.cc
+++ b/internal/ceres/trust_region_minimizer.cc
@@ -136,8 +136,8 @@
                                 double* parameters,
                                 Solver::Summary* solver_summary) {
   options_ = options;
-  sort(options_.trust_region_minimizer_iterations_to_dump.begin(),
-       options_.trust_region_minimizer_iterations_to_dump.end());
+  std::sort(options_.trust_region_minimizer_iterations_to_dump.begin(),
+            options_.trust_region_minimizer_iterations_to_dump.end());
 
   parameters_ = parameters;
 
@@ -165,7 +165,6 @@
   num_consecutive_invalid_steps_ = 0;
 
   x_ = ConstVectorRef(parameters_, num_parameters_);
-  x_norm_ = x_.norm();
   residuals_.resize(num_residuals_);
   trust_region_step_.resize(num_effective_parameters_);
   delta_.resize(num_effective_parameters_);
@@ -179,7 +178,6 @@
   // the Jacobian, we will compute and overwrite this vector.
   jacobian_scaling_ = Vector::Ones(num_effective_parameters_);
 
-  x_norm_ = -1;  // Invalid value
   x_cost_ = std::numeric_limits<double>::max();
   minimum_cost_ = x_cost_;
   model_cost_change_ = 0.0;
@@ -213,7 +211,6 @@
     }
 
     x_ = candidate_x_;
-    x_norm_ = x_.norm();
   }
 
   if (!EvaluateGradientAndJacobian(/*new_evaluation_point=*/true)) {
@@ -704,10 +701,12 @@
 
 // Solver::Options::parameter_tolerance based convergence check.
 bool TrustRegionMinimizer::ParameterToleranceReached() {
+  const double x_norm = x_.norm();
+
   // Compute the norm of the step in the ambient space.
   iteration_summary_.step_norm = (x_ - candidate_x_).norm();
   const double step_size_tolerance =
-      options_.parameter_tolerance * (x_norm_ + options_.parameter_tolerance);
+      options_.parameter_tolerance * (x_norm + options_.parameter_tolerance);
 
   if (iteration_summary_.step_norm > step_size_tolerance) {
     return false;
@@ -716,7 +715,7 @@
   solver_summary_->message = StringPrintf(
       "Parameter tolerance reached. "
       "Relative step_norm: %e <= %e.",
-      (iteration_summary_.step_norm / (x_norm_ + options_.parameter_tolerance)),
+      (iteration_summary_.step_norm / (x_norm + options_.parameter_tolerance)),
       options_.parameter_tolerance);
   solver_summary_->termination_type = CONVERGENCE;
   if (is_not_silent_) {
@@ -809,7 +808,6 @@
 // evaluator know that the step has been accepted.
 bool TrustRegionMinimizer::HandleSuccessfulStep() {
   x_ = candidate_x_;
-  x_norm_ = x_.norm();
 
   // Since the step was successful, this point has already had the residual
   // evaluated (but not the jacobian). So indicate that to the evaluator.

internal/ceres/trust_region_minimizer.h

diff --git a/internal/ceres/trust_region_minimizer.h b/internal/ceres/trust_region_minimizer.h
index a7b2130..07feb82 100644
--- a/internal/ceres/trust_region_minimizer.h
+++ b/internal/ceres/trust_region_minimizer.h
@@ -138,8 +138,6 @@
   // 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.