New Trust region loop.
1. New TrustRegionMinimizer and basic tests for it.
2. New TrustRegionStrategy interface.
3. New LevenbergMarquardtStrategy and tests for it.
4. Updates to SolverImpl to reflect this.
5. Changes to Solver::Options and IterationSummary related to this.
6. Deleted levenberg_marquardt.cc/h/_test.cc
Change-Id: I6c1d1a7c774f014856f9f26263a830aa886e1400
diff --git a/include/ceres/iteration_callback.h b/include/ceres/iteration_callback.h
index 88da992..6d7720c 100644
--- a/include/ceres/iteration_callback.h
+++ b/include/ceres/iteration_callback.h
@@ -28,8 +28,9 @@
//
// Author: sameeragarwal@google.com (Sameer Agarwal)
//
-// When an iteration callback is specified, Ceres calls the callback after each
-// optimizer step and pass it an IterationSummary object, defined below.
+// When an iteration callback is specified, Ceres calls the callback
+// after each minimizer step (if the minimizer has not converged) and
+// passes it an IterationSummary object, defined below.
#ifndef CERES_PUBLIC_ITERATION_CALLBACK_H_
#define CERES_PUBLIC_ITERATION_CALLBACK_H_
@@ -44,7 +45,15 @@
// Current iteration number.
int32 iteration;
+ // Step was numerically valid, i.e., all values are finite and the
+ // step reduces the value of the linearized model.
+ //
+ // Note: step_is_valid is false when iteration = 0.
+ bool step_is_valid;
+
// Whether or not the algorithm made progress in this iteration.
+ //
+ // Note: step_is_successful is false when iteration = 0.
bool step_is_successful;
// Value of the objective function.
@@ -66,9 +75,10 @@
// cost and the change in the cost of the linearized approximation.
double relative_decrease;
- // Value of the regularization parameter for Levenberg-Marquardt
- // algorithm at the end of the current iteration.
- double mu;
+ // Size of the trust region at the end of the current iteration. For
+ // the Levenberg-Marquardt algorithm, the regularization parameter
+ // mu = 1.0 / trust_region_radius.
+ double trust_region_radius;
// For the inexact step Levenberg-Marquardt algorithm, this is the
// relative accuracy with which the Newton(LM) step is solved. This
@@ -81,13 +91,15 @@
// Newton step.
int linear_solver_iterations;
- // TODO(sameeragarwal): Change to use a higher precision timer using
- // clock_gettime.
- // Time (in seconds) spent inside the linear least squares solver.
+ // TODO(sameeragarwal): Change the following two to use a higher
+ // precision timer using clock_gettime.
+ //
+ // Time (in seconds) spent inside the minimizer loop in the current
+ // iteration.
int iteration_time_sec;
- // Time (in seconds) spent inside the linear least squares solver.
- int linear_solver_time_sec;
+ // Time (in seconds) spent inside the trust region step solver.
+ int step_solver_time_sec;
};
// Interface for specifying callbacks that are executed at the end of
@@ -133,7 +145,7 @@
// summary.gradient_max_norm,
// summary.step_norm,
// summary.relative_decrease,
-// summary.mu,
+// summary.trust_region_radius,
// summary.eta,
// summary.linear_solver_iterations);
// if (log_to_stdout_) {
diff --git a/include/ceres/solver.h b/include/ceres/solver.h
index 701f0b2..ed4c9b8 100644
--- a/include/ceres/solver.h
+++ b/include/ceres/solver.h
@@ -57,13 +57,17 @@
struct Options {
// Default constructor that sets up a generic sparse problem.
Options() {
- minimizer_type = LEVENBERG_MARQUARDT;
+ trust_region_strategy_type = LEVENBERG_MARQUARDT;
max_num_iterations = 50;
- max_solver_time_sec = 1.0e9;
+ max_solver_time_sec = 1e9;
num_threads = 1;
- tau = 1e-4;
- min_mu = 1e-20;
+ initial_trust_region_radius = 1e4;
+ max_trust_region_radius = 1e16;
+ min_trust_region_radius = 1e-32;
min_relative_decrease = 1e-3;
+ lm_min_diagonal = 1e-6;
+ lm_max_diagonal = 1e32;
+ max_num_consecutive_invalid_steps = 5;
function_tolerance = 1e-6;
gradient_tolerance = 1e-10;
parameter_tolerance = 1e-8;
@@ -93,7 +97,6 @@
return_final_residuals = false;
lsqp_dump_directory = "/tmp";
lsqp_dump_format_type = TEXTFILE;
- crash_and_dump_lsqp_on_failure = false;
check_gradients = false;
gradient_check_relative_precision = 1e-8;
numeric_derivative_relative_step_size = 1e-6;
@@ -102,7 +105,7 @@
// Minimizer options ----------------------------------------
- MinimizerType minimizer_type;
+ TrustRegionStrategyType trust_region_strategy_type;
// Maximum number of iterations for the minimizer to run for.
int max_num_iterations;
@@ -114,27 +117,35 @@
// jacobians.
int num_threads;
- // For Levenberg-Marquardt, the initial value for the
- // regularizer. This is the inversely related to the size of the
- // initial trust region.
- double tau;
+ // Trust region minimizer settings.
+ double initial_trust_region_radius;
+ double max_trust_region_radius;
- // For Levenberg-Marquardt, the minimum value of the
- // regularizer. For well constrained problems there shold be no
- // need to modify the default value, but in some cases, going
- // below a certain minimum reliably triggers rank deficiency in
- // the normal equations. In such cases, the LM solver can
- // oscillate between lowering the value of mu, seeing a numerical
- // failure, and then increasing it making some progress and then
- // reducing it again.
- //
- // In such cases, it is useful to set a higher value for min_mu.
- double min_mu;
+ // Minimizer terminates when the trust region radius becomes
+ // smaller than this value.
+ double min_trust_region_radius;
- // For trust region methods, this is lower threshold for the
- // relative decrease before a step is accepted.
+ // Lower bound for the relative decrease before a step is
+ // accepted.
double min_relative_decrease;
+ // For the Levenberg-Marquadt algorithm, the scaled diagonal of
+ // the normal equations J'J is used to control the size of the
+ // trust region. Extremely small and large values along the
+ // diagonal can make this regularization scheme
+ // fail. lm_max_diagonal and lm_min_diagonal, clamp the values of
+ // diag(J'J) from above and below. In the normal course of
+ // operation, the user should not have to modify these parameters.
+ double lm_min_diagonal;
+ double lm_max_diagonal;
+
+ // Sometimes due to numerical conditioning problems or linear
+ // solver flakiness, the trust region strategy may return a
+ // numerically invalid step that can be fixed by reducing the
+ // trust region size. So the TrustRegionMinimizer allows for a few
+ // successive invalid steps before it declares NUMERICAL_FAILURE.
+ int max_num_consecutive_invalid_steps;
+
// Minimizer terminates when
//
// (new_cost - old_cost) < function_tolerance * old_cost;
@@ -243,15 +254,6 @@
string lsqp_dump_directory;
DumpFormatType lsqp_dump_format_type;
- // Dump the linear least squares problem to disk if the minimizer
- // fails due to NUMERICAL_FAILURE and crash the process. This flag
- // is useful for generating debugging information. The problem is
- // dumped in a file whose name is determined by
- // Solver::Options::lsqp_dump_format.
- //
- // Note: This requires a version of Ceres built with protocol buffers.
- bool crash_and_dump_lsqp_on_failure;
-
// Finite differences options ----------------------------------------------
// Check all jacobians computed by each residual block with finite
@@ -299,10 +301,15 @@
bool update_state_every_iteration;
// Callbacks that are executed at the end of each iteration of the
- // Minimizer. They are executed in the order that they are
- // specified in this vector. By default, parameter blocks are
- // updated only at the end of the optimization, i.e when the
- // Minimizer terminates. This behaviour is controlled by
+ // Minimizer. An iteration may terminate midway, either due to
+ // numerical failures or because one of the convergence tests has
+ // been satisfied. In this case none of the callbacks are
+ // executed.
+
+ // Callbacks are executed in the order that they are specified in
+ // this vector. By default, parameter blocks are updated only at
+ // the end of the optimization, i.e when the Minimizer
+ // terminates. This behaviour is controlled by
// update_state_every_variable. If the user wishes to have access
// to the update parameter blocks when his/her callbacks are
// executed, then set update_state_every_iteration to true.
diff --git a/include/ceres/types.h b/include/ceres/types.h
index 61a9a0d..705097f 100644
--- a/include/ceres/types.h
+++ b/include/ceres/types.h
@@ -158,8 +158,8 @@
PER_MINIMIZER_ITERATION
};
-enum MinimizerType {
- LEVENBERG_MARQUARDT
+enum TrustRegionStrategyType {
+ LEVENBERG_MARQUARDT,
};
enum SolverTerminationType {
