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) {