commit d4cb94b6d6fca199ce6aba24ea91317027484e91
author Sameer Agarwal <sameeragarwal@google.com> Wed May 22 09:13:27 2013 -0700
committer Gerrit Code Review <noreply-gerritcodereview@google.com> Wed May 22 20:04:57 2013 +0000
tree 9531164d93a58b04d2f4e16027814c93fb697178
parent 07f208fd6d7fa06571e5dceb072c2f270d148193

Add adaptive stopping to inner iterations.

Change-Id: I83c909b8b87f1320aa30dcc80ac43a63765b9181

include/ceres/solver.h

diff --git a/include/ceres/solver.h b/include/ceres/solver.h
index 0603a30..8f394ea 100644
--- a/include/ceres/solver.h
+++ b/include/ceres/solver.h
@@ -98,6 +98,7 @@
       linear_solver_ordering = NULL;
       use_postordering = false;
       use_inner_iterations = false;
+      inner_iteration_tolerance = 1e-3;
       inner_iteration_ordering = NULL;
       linear_solver_min_num_iterations = 1;
       linear_solver_max_num_iterations = 500;
@@ -443,6 +444,16 @@
     //    number groups. Each group must be an independent set.
     ParameterBlockOrdering* inner_iteration_ordering;
 
+    // Generally speaking, inner iterations make significant progress
+    // in the early stages of the solve and then their contribution
+    // drops down sharply, at which point the time spent doing inner
+    // iterations is not worth it.
+    //
+    // Once the relative decrease in the objective function drops
+    // below inner_iteration_tolerance, the use of inner iterations
+    // in subsequent trust region minimizer iterations is disabled.
+    double inner_iteration_tolerance;
+
     // Minimum number of iterations for which the linear solver should
     // run, even if the convergence criterion is satisfied.
     int linear_solver_min_num_iterations;

internal/ceres/minimizer.h

diff --git a/internal/ceres/minimizer.h b/internal/ceres/minimizer.h
index 040ddd9..18ce64d 100644
--- a/internal/ceres/minimizer.h
+++ b/internal/ceres/minimizer.h
@@ -89,6 +89,7 @@
       jacobian = NULL;
       callbacks = options.callbacks;
       inner_iteration_minimizer = NULL;
+      inner_iteration_tolerance = options.inner_iteration_tolerance;
     }
 
     int max_num_iterations;
@@ -141,6 +142,7 @@
     SparseMatrix* jacobian;
 
     Minimizer* inner_iteration_minimizer;
+    double inner_iteration_tolerance;
   };
 
   static bool RunCallbacks(const vector<IterationCallback*> callbacks,

internal/ceres/trust_region_minimizer.cc

diff --git a/internal/ceres/trust_region_minimizer.cc b/internal/ceres/trust_region_minimizer.cc
index 7d4c093..ab0f44b 100644
--- a/internal/ceres/trust_region_minimizer.cc
+++ b/internal/ceres/trust_region_minimizer.cc
@@ -191,6 +191,7 @@
   }
 
   int num_consecutive_invalid_steps = 0;
+  bool inner_iterations_are_enabled = options.inner_iteration_minimizer != NULL;
   while (true) {
     if (!RunCallbacks(options.callbacks, iteration_summary, summary)) {
       return;
@@ -317,7 +318,7 @@
         new_cost = numeric_limits<double>::max();
       } else {
         // Check if performing an inner iteration will make it better.
-        if (options.inner_iteration_minimizer != NULL) {
+        if (inner_iterations_are_enabled) {
           const double x_plus_delta_cost = new_cost;
           Vector inner_iteration_x = x_plus_delta;
           Solver::Summary inner_iteration_summary;
@@ -337,6 +338,18 @@
             VLOG(2) << "Inner iteration succeeded; current cost: " << cost
                     << " x_plus_delta_cost: " << x_plus_delta_cost
                     << " new_cost: " << new_cost;
+            const double inner_iteration_relative_progress =
+                (x_plus_delta_cost - new_cost) / x_plus_delta_cost;
+            inner_iterations_are_enabled =
+                (inner_iteration_relative_progress >
+                 options.inner_iteration_tolerance);
+
+            // Disable inner iterations once the relative improvement
+            // drops below tolerance.
+            if (!inner_iterations_are_enabled) {
+              LOG(INFO) << "Disabling inner iterations. Progress : "
+                        << inner_iteration_relative_progress;
+            }
           }
         }
       }
@@ -356,7 +369,6 @@
         return;
       }
 
-      VLOG(2) << "old cost: " << cost << " new cost: " << new_cost;
       iteration_summary.cost_change =  cost - new_cost;
       const double absolute_function_tolerance =
           options_.function_tolerance * cost;