Expose line search parameters in Solver::Options.
Change-Id: Ifc52980976e7bac73c8164d80518a5a19db1b79d
diff --git a/docs/source/solving.rst b/docs/source/solving.rst
index 254c120..9f6cb6b 100644
--- a/docs/source/solving.rst
+++ b/docs/source/solving.rst
@@ -819,6 +819,42 @@
rank. The best choice usually requires some problem specific
experimentation.
+.. member:: LineSearchIterpolationType Solver::Options::line_search_interpolation_type
+
+ Default: ``CUBIC``
+
+ Degree of the polynomial used to approximate the objective
+ function. Valid values are ``BISECTION``, ``QUADRATIC`` and
+ ``CUBIC``.
+
+.. member:: double Solver::Options::min_line_search_step_size
+
+ If during the line search, the step size falls below this value, it
+ is truncated to zero.
+
+.. member:: double Solver::Options::armijo_sufficient_decrease
+
+ Solving the line search problem exactly is computationally
+ prohibitive. Fortunately, line search based optimization algorithms
+ can still guarantee convergence if instead of an exact solution,
+ the line search algorithm returns a solution which decreases the
+ value of the objective function sufficiently. More precisely, we
+ are looking for a step size s.t.
+
+ .. math:: f(\text{step_size}) \le f(0) + \text{sufficient_decrease} * [f'(0) * \text{step_size}]
+
+.. member:: double Solver::Options::min_armijo_relative_step_size_change
+
+ In each iteration of the Armijo line search,
+
+ .. math:: \text{new_step_size} \ge \text{min_relative_step_size_change} * \text{step_size}
+
+.. member:: double Solver::Options::max_armijo_relative_step_size_change
+
+ In each iteration of the Armijo line search,
+
+ .. math:: \text{new_step_size} \le \text{max_relative_step_size_change} * \text{step_size}
+
.. member:: TrustRegionStrategyType Solver::Options::trust_region_strategy_type
Default: ``LEVENBERG_MARQUARDT``
diff --git a/include/ceres/solver.h b/include/ceres/solver.h
index a86a586..8bebf9b 100644
--- a/include/ceres/solver.h
+++ b/include/ceres/solver.h
@@ -63,6 +63,12 @@
line_search_type = ARMIJO;
nonlinear_conjugate_gradient_type = FLETCHER_REEVES;
max_lbfgs_rank = 20;
+ line_search_interpolation_type = CUBIC;
+ min_line_search_step_size = 1e-9;
+ armijo_sufficient_decrease = 1e-4;
+ min_armijo_relative_step_size_change = 1e-3;
+ max_armijo_relative_step_size_change = 0.6;
+
trust_region_strategy_type = LEVENBERG_MARQUARDT;
dogleg_type = TRADITIONAL_DOGLEG;
use_nonmonotonic_steps = false;
@@ -172,6 +178,43 @@
// Limited Storage". Mathematics of Computation 35 (151): 773–782.
int max_lbfgs_rank;
+ // Degree of the polynomial used to approximate the objective
+ // function. Valid values are BISECTION, QUADRATIC and CUBIC.
+ //
+ // BISECTION corresponds to pure backtracking search with no
+ // interpolation.
+ LineSearchInterpolationType line_search_interpolation_type;
+
+ // If during the line search, the step_size falls below this
+ // value, it is truncated to zero.
+ double min_line_search_step_size;
+
+ // Armijo line search parameters.
+
+ // Solving the line search problem exactly is computationally
+ // prohibitive. Fortunately, line search based optimization
+ // algorithms can still guarantee convergence if instead of an
+ // exact solution, the line search algorithm returns a solution
+ // which decreases the value of the objective function
+ // sufficiently. More precisely, we are looking for a step_size
+ // s.t.
+ //
+ // f(step_size) <= f(0) + sufficient_decrease * f'(0) * step_size
+ //
+ double armijo_sufficient_decrease;
+
+ // In each iteration of the Armijo line search,
+ //
+ // new_step_size >= min_relative_step_size_change * step_size
+ //
+ double min_armijo_relative_step_size_change;
+
+ // In each iteration of the Armijo line search,
+ //
+ // new_step_size <= max_relative_step_size_change * step_size
+ //
+ double max_armijo_relative_step_size_change;
+
TrustRegionStrategyType trust_region_strategy_type;
// Type of dogleg strategy to use.
@@ -673,6 +716,7 @@
LineSearchDirectionType line_search_direction_type;
LineSearchType line_search_type;
+
int max_lbfgs_rank;
};
diff --git a/include/ceres/types.h b/include/ceres/types.h
index 5edd128..5becb53 100644
--- a/include/ceres/types.h
+++ b/include/ceres/types.h
@@ -332,6 +332,12 @@
FORWARD
};
+enum LineSearchInterpolationType {
+ BISECTION,
+ QUADRATIC,
+ CUBIC
+};
+
const char* LinearSolverTypeToString(LinearSolverType type);
bool StringToLinearSolverType(string value, LinearSolverType* type);
@@ -364,7 +370,14 @@
const char* NonlinearConjugateGradientTypeToString(
NonlinearConjugateGradientType type);
bool StringToNonlinearConjugateGradientType(
- string value, NonlinearConjugateGradientType* type);
+ string value,
+ NonlinearConjugateGradientType* type);
+
+const char* LineSearchInterpolationTypeToString(
+ LineSearchInterpolationType type);
+bool StringToLineSearchInterpolationType(
+ string value,
+ LineSearchInterpolationType* type);
const char* LinearSolverTerminationTypeToString(
LinearSolverTerminationType type);
diff --git a/internal/ceres/line_search.cc b/internal/ceres/line_search.cc
index bc47814..06c823f 100644
--- a/internal/ceres/line_search.cc
+++ b/internal/ceres/line_search.cc
@@ -125,7 +125,7 @@
step_size_is_valid =
function->Evaluate(step_size,
&cost,
- options.interpolation_degree < 2 ? NULL : &gradient);
+ options.interpolation_type != CUBIC ? NULL : &gradient);
while (!step_size_is_valid || cost > (initial_cost
+ options.sufficient_decrease
* initial_gradient
@@ -137,26 +137,22 @@
const double current_step_size = step_size;
// Backtracking search. Each iteration of this loop finds a new point
- if ((options.interpolation_degree == 0) || !step_size_is_valid) {
- // Backtrack by halving the step_size;
+ if ((options.interpolation_type == BISECTION) || !step_size_is_valid) {
step_size *= 0.5;
} else {
// Backtrack by interpolating the function and gradient values
// and minimizing the corresponding polynomial.
-
vector<FunctionSample> samples;
samples.push_back(ValueAndGradientSample(0.0,
initial_cost,
initial_gradient));
- if (options.interpolation_degree == 1) {
+ if (options.interpolation_type == QUADRATIC) {
// Two point interpolation using function values and the
// initial gradient.
samples.push_back(ValueSample(step_size, cost));
- if (options.use_higher_degree_interpolation_when_possible &&
- summary->num_evaluations > 1 &&
- previous_step_size_is_valid) {
+ if (summary->num_evaluations > 1 && previous_step_size_is_valid) {
// Three point interpolation, using function values and the
// initial gradient.
samples.push_back(ValueSample(previous_step_size, previous_cost));
@@ -167,9 +163,7 @@
cost,
gradient));
- if (options.use_higher_degree_interpolation_when_possible &&
- summary->num_evaluations > 1 &&
- previous_step_size_is_valid) {
+ if (summary->num_evaluations > 1 && previous_step_size_is_valid) {
// Three point interpolation using the function values and
// the gradients.
samples.push_back(ValueAndGradientSample(previous_step_size,
@@ -191,7 +185,7 @@
previous_cost = cost;
previous_gradient = gradient;
- if (fabs(initial_gradient) * step_size < options.step_size_threshold) {
+ if (fabs(initial_gradient) * step_size < options.min_step_size) {
LOG(WARNING) << "Line search failed: step_size too small: " << step_size;
return;
}
@@ -200,7 +194,7 @@
step_size_is_valid =
function->Evaluate(step_size,
&cost,
- options.interpolation_degree < 2 ? NULL : &gradient);
+ options.interpolation_type != CUBIC ? NULL : &gradient);
}
summary->optimal_step_size = step_size;
diff --git a/internal/ceres/line_search.h b/internal/ceres/line_search.h
index a2b59b1..5792652 100644
--- a/internal/ceres/line_search.h
+++ b/internal/ceres/line_search.h
@@ -38,6 +38,7 @@
#include <vector>
#include "ceres/internal/eigen.h"
#include "ceres/internal/port.h"
+#include "ceres/types.h"
namespace ceres {
namespace internal {
@@ -60,30 +61,16 @@
struct Options {
Options()
- : interpolation_degree(1),
- use_higher_degree_interpolation_when_possible(false),
+ : interpolation_type(CUBIC),
sufficient_decrease(1e-4),
min_relative_step_size_change(1e-3),
- max_relative_step_size_change(0.6),
- step_size_threshold(1e-9),
+ max_relative_step_size_change(0.9),
+ min_step_size(1e-9),
function(NULL) {}
- // TODO(sameeragarwal): Replace this with enums which are common
- // across various line searches.
- //
// Degree of the polynomial used to approximate the objective
- // function. Valid values are {0, 1, 2}.
- //
- // For Armijo line search
- //
- // 0: Bisection based backtracking search.
- // 1: Quadratic interpolation.
- // 2: Cubic interpolation.
- int interpolation_degree;
-
- // Usually its possible to increase the degree of the
- // interpolation polynomial by storing and using an extra point.
- bool use_higher_degree_interpolation_when_possible;
+ // function.
+ LineSearchInterpolationType interpolation_type;
// Armijo line search parameters.
@@ -110,7 +97,7 @@
// If during the line search, the step_size falls below this
// value, it is truncated to zero.
- double step_size_threshold;
+ double min_step_size;
// The one dimensional function that the line search algorithm
// minimizes.
diff --git a/internal/ceres/line_search_minimizer.cc b/internal/ceres/line_search_minimizer.cc
index 92b7965..24aada3 100644
--- a/internal/ceres/line_search_minimizer.cc
+++ b/internal/ceres/line_search_minimizer.cc
@@ -164,11 +164,19 @@
LineSearchDirection::Create(line_search_direction_options));
LineSearchFunction line_search_function(evaluator);
+
LineSearch::Options line_search_options;
+ line_search_options.interpolation_type =
+ options.line_search_interpolation_type;
+ line_search_options.min_step_size = options.min_line_search_step_size;
+ line_search_options.sufficient_decrease =
+ options.armijo_sufficient_decrease;
+ line_search_options.min_relative_step_size_change =
+ options.min_armijo_relative_step_size_change;
+ line_search_options.max_relative_step_size_change =
+ options.max_armijo_relative_step_size_change;
line_search_options.function = &line_search_function;
- // TODO(sameeragarwal): Make this parameterizable over different
- // line searches.
ArmijoLineSearch line_search;
LineSearch::Summary line_search_summary;
diff --git a/internal/ceres/minimizer.h b/internal/ceres/minimizer.h
index f8f8a96..300d2df 100644
--- a/internal/ceres/minimizer.h
+++ b/internal/ceres/minimizer.h
@@ -88,6 +88,14 @@
nonlinear_conjugate_gradient_type =
options.nonlinear_conjugate_gradient_type;
max_lbfgs_rank = options.max_lbfgs_rank;
+ line_search_interpolation_type =
+ options.line_search_interpolation_type;
+ min_line_search_step_size = options.min_line_search_step_size;
+ armijo_sufficient_decrease = options.armijo_sufficient_decrease;
+ min_armijo_relative_step_size_change =
+ options.min_armijo_relative_step_size_change;
+ max_armijo_relative_step_size_change =
+ options.max_armijo_relative_step_size_change;
evaluator = NULL;
trust_region_strategy = NULL;
jacobian = NULL;
@@ -123,6 +131,12 @@
LineSearchType line_search_type;
NonlinearConjugateGradientType nonlinear_conjugate_gradient_type;
int max_lbfgs_rank;
+ LineSearchInterpolationType line_search_interpolation_type;
+ double min_line_search_step_size;
+ double armijo_sufficient_decrease;
+ double min_armijo_relative_step_size_change;
+ double max_armijo_relative_step_size_change;
+
// List of callbacks that are executed by the Minimizer at the end
// of each iteration.
diff --git a/internal/ceres/types.cc b/internal/ceres/types.cc
index 2e19322..e88cdd6 100644
--- a/internal/ceres/types.cc
+++ b/internal/ceres/types.cc
@@ -193,6 +193,27 @@
return false;
}
+const char* LineSearchInterpolationTypeToString(
+ LineSearchInterpolationType type) {
+ switch (type) {
+ CASESTR(BISECTION);
+ CASESTR(QUADRATIC);
+ CASESTR(CUBIC);
+ default:
+ return "UNKNOWN";
+ }
+}
+
+bool StringToLineSearchInterpolationType(
+ string value,
+ LineSearchInterpolationType* type) {
+ UpperCase(&value);
+ STRENUM(BISECTION);
+ STRENUM(QUADRATIC);
+ STRENUM(CUBIC);
+ return false;
+}
+
const char* NonlinearConjugateGradientTypeToString(
NonlinearConjugateGradientType type) {
switch (type) {
