Add a lower bound on the regularization constant in LM.
In some cases the Levenberg-Marquardt can oscillate between,
two values of the regularizer mu. A small value which causes
the linear solver to fail and a higher value at which the solver
makes progress. This can cause significant wastage of solver
effort, and mu should just be clamped to some value.
This CL provides this setting as Solver::Options::min_mu,
and updates the documentation to reflect this.
diff --git a/docs/api.tex b/docs/api.tex
index c8feeeb..471f2de 100644
--- a/docs/api.tex
+++ b/docs/api.tex
@@ -462,6 +462,16 @@
\item{\texttt{tau}}(\texttt{1e-4}) Initial value of the regularization parameter $\mu$ used by the Levenberg-Marquardt algorithm. The size of this parameter indicate the user's guess of how far the initial solution is from the minimum. Large values indicates that the solution is far away.
+\item{\texttt{min\_mu}(\texttt{1e-20})} 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 Levenberg-Marquardt algorithm 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 \texttt{min\_mu}.
\item{\texttt{min\_relative\_decrease}}(\texttt{1e-3}) Lower threshold for relative decrease before a Levenberg-Marquardt step is acceped.
diff --git a/include/ceres/solver.h b/include/ceres/solver.h
index bd66927..be81768 100644
--- a/include/ceres/solver.h
+++ b/include/ceres/solver.h
@@ -62,6 +62,7 @@
max_solver_time_sec = 1.0e9;
num_threads = 1;
tau = 1e-4;
+ min_mu = 1e-20;
min_relative_decrease = 1e-3;
function_tolerance = 1e-6;
gradient_tolerance = 1e-10;
@@ -111,6 +112,18 @@
// initial trust region.
double tau;
+ // 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;
+
// For trust region methods, this is lower threshold for the
// relative decrease before a step is accepted.
double min_relative_decrease;
diff --git a/internal/ceres/levenberg_marquardt.cc b/internal/ceres/levenberg_marquardt.cc
index 7d3afac..1eae624 100644
--- a/internal/ceres/levenberg_marquardt.cc
+++ b/internal/ceres/levenberg_marquardt.cc
@@ -498,6 +498,7 @@
}
mu = mu * max(1.0 / 3.0, 1 - pow(2 * relative_decrease - 1, 3));
+ mu = std::max(options.min_mu, mu);
nu = 2.0;
step_is_successful = true;
break;
diff --git a/internal/ceres/minimizer.h b/internal/ceres/minimizer.h
index 77cb00c..19b0344 100644
--- a/internal/ceres/minimizer.h
+++ b/internal/ceres/minimizer.h
@@ -57,6 +57,7 @@
min_relative_decrease = options.min_relative_decrease;
eta = options.eta;
tau = options.tau;
+ min_mu = options.min_mu;
jacobi_scaling = options.jacobi_scaling;
crash_and_dump_lsqp_on_failure = options.crash_and_dump_lsqp_on_failure;
lsqp_dump_directory = options.lsqp_dump_directory;
@@ -74,6 +75,7 @@
double min_relative_decrease;
double eta;
double tau;
+ double min_mu;
bool jacobi_scaling;
bool crash_and_dump_lsqp_on_failure;
vector<int> lsqp_iterations_to_dump;
