diff options
Diffstat (limited to 'extern/ceres/internal/ceres/line_search.h')
| -rw-r--r-- | extern/ceres/internal/ceres/line_search.h | 98 |
1 files changed, 39 insertions, 59 deletions
diff --git a/extern/ceres/internal/ceres/line_search.h b/extern/ceres/internal/ceres/line_search.h index 6a21cbeac11..d59fd777367 100644 --- a/extern/ceres/internal/ceres/line_search.h +++ b/extern/ceres/internal/ceres/line_search.h @@ -35,6 +35,7 @@ #include <string> #include <vector> +#include "ceres/function_sample.h" #include "ceres/internal/eigen.h" #include "ceres/internal/port.h" #include "ceres/types.h" @@ -43,7 +44,6 @@ namespace ceres { namespace internal { class Evaluator; -struct FunctionSample; class LineSearchFunction; // Line search is another name for a one dimensional optimization @@ -51,7 +51,7 @@ class LineSearchFunction; // dimensional optimization problems that arise as subproblems of // general multidimensional optimization problems. // -// While finding the exact minimum of a one dimensionl function is +// While finding the exact minimum of a one dimensional function is // hard, instances of LineSearch find a point that satisfies a // sufficient decrease condition. Depending on the particular // condition used, we get a variety of different line search @@ -61,21 +61,9 @@ class LineSearch { struct Summary; struct Options { - Options() - : interpolation_type(CUBIC), - sufficient_decrease(1e-4), - max_step_contraction(1e-3), - min_step_contraction(0.9), - min_step_size(1e-9), - max_num_iterations(20), - sufficient_curvature_decrease(0.9), - max_step_expansion(10.0), - is_silent(false), - function(NULL) {} - // Degree of the polynomial used to approximate the objective // function. - LineSearchInterpolationType interpolation_type; + LineSearchInterpolationType interpolation_type = CUBIC; // Armijo and Wolfe line search parameters. @@ -88,7 +76,7 @@ class LineSearch { // s.t. // // f(step_size) <= f(0) + sufficient_decrease * f'(0) * step_size - double sufficient_decrease; + double sufficient_decrease = 1e-4; // In each iteration of the Armijo / Wolfe line search, // @@ -98,7 +86,7 @@ class LineSearch { // // 0 < max_step_contraction < min_step_contraction < 1 // - double max_step_contraction; + double max_step_contraction = 1e-3; // In each iteration of the Armijo / Wolfe line search, // @@ -107,16 +95,16 @@ class LineSearch { // // 0 < max_step_contraction < min_step_contraction < 1 // - double min_step_contraction; + double min_step_contraction = 0.9; // If during the line search, the step_size falls below this // value, it is truncated to zero. - double min_step_size; + double min_step_size = 1e-9; // Maximum number of trial step size iterations during each line search, // if a step size satisfying the search conditions cannot be found within // this number of trials, the line search will terminate. - int max_num_iterations; + int max_num_iterations = 20; // Wolfe-specific line search parameters. @@ -131,7 +119,7 @@ class LineSearch { // // Where f() is the line search objective and f'() is the derivative // of f w.r.t step_size (d f / d step_size). - double sufficient_curvature_decrease; + double sufficient_curvature_decrease = 0.9; // During the bracketing phase of the Wolfe search, the step size is // increased until either a point satisfying the Wolfe conditions is @@ -142,43 +130,32 @@ class LineSearch { // new_step_size <= max_step_expansion * step_size. // // By definition for expansion, max_step_expansion > 1.0. - double max_step_expansion; + double max_step_expansion = 10; - bool is_silent; + bool is_silent = false; // The one dimensional function that the line search algorithm // minimizes. - LineSearchFunction* function; + LineSearchFunction* function = nullptr; }; // Result of the line search. struct Summary { - Summary() - : success(false), - optimal_step_size(0.0), - num_function_evaluations(0), - num_gradient_evaluations(0), - num_iterations(0), - cost_evaluation_time_in_seconds(-1.0), - gradient_evaluation_time_in_seconds(-1.0), - polynomial_minimization_time_in_seconds(-1.0), - total_time_in_seconds(-1.0) {} - - bool success; - double optimal_step_size; - int num_function_evaluations; - int num_gradient_evaluations; - int num_iterations; + bool success = false; + FunctionSample optimal_point; + int num_function_evaluations = 0; + int num_gradient_evaluations = 0; + int num_iterations = 0; // Cumulative time spent evaluating the value of the cost function across // all iterations. - double cost_evaluation_time_in_seconds; + double cost_evaluation_time_in_seconds = 0.0; // Cumulative time spent evaluating the gradient of the cost function across // all iterations. - double gradient_evaluation_time_in_seconds; + double gradient_evaluation_time_in_seconds = 0.0; // Cumulative time spent minimizing the interpolating polynomial to compute // the next candidate step size across all iterations. - double polynomial_minimization_time_in_seconds; - double total_time_in_seconds; + double polynomial_minimization_time_in_seconds = 0.0; + double total_time_in_seconds = 0.0; std::string error; }; @@ -234,6 +211,7 @@ class LineSearchFunction { public: explicit LineSearchFunction(Evaluator* evaluator); void Init(const Vector& position, const Vector& direction); + // Evaluate the line search objective // // f(x) = p(position + x * direction) @@ -241,27 +219,29 @@ class LineSearchFunction { // Where, p is the objective function of the general optimization // problem. // - // g is the gradient f'(x) at x. + // evaluate_gradient controls whether the gradient will be evaluated + // or not. // - // f must not be null. The gradient is computed only if g is not null. - bool Evaluate(double x, double* f, double* g); + // On return output->*_is_valid indicate indicate whether the + // corresponding fields have numerically valid values or not. + void Evaluate(double x, bool evaluate_gradient, FunctionSample* output); + double DirectionInfinityNorm() const; + // Resets to now, the start point for the results from TimeStatistics(). void ResetTimeStatistics(); void TimeStatistics(double* cost_evaluation_time_in_seconds, double* gradient_evaluation_time_in_seconds) const; + const Vector& position() const { return position_; } + const Vector& direction() const { return direction_; } private: Evaluator* evaluator_; Vector position_; Vector direction_; - // evaluation_point = Evaluator::Plus(position_, x * direction_); - Vector evaluation_point_; - // scaled_direction = x * direction_; Vector scaled_direction_; - Vector gradient_; // We may not exclusively own the evaluator (e.g. in the Trust Region // minimizer), hence we need to save the initial evaluation durations for the @@ -282,10 +262,10 @@ class ArmijoLineSearch : public LineSearch { virtual ~ArmijoLineSearch() {} private: - virtual void DoSearch(double step_size_estimate, - double initial_cost, - double initial_gradient, - Summary* summary) const; + void DoSearch(double step_size_estimate, + double initial_cost, + double initial_gradient, + Summary* summary) const final; }; // Bracketing / Zoom Strong Wolfe condition line search. This implementation @@ -315,10 +295,10 @@ class WolfeLineSearch : public LineSearch { Summary* summary) const; private: - virtual void DoSearch(double step_size_estimate, - double initial_cost, - double initial_gradient, - Summary* summary) const; + void DoSearch(double step_size_estimate, + double initial_cost, + double initial_gradient, + Summary* summary) const final; }; } // namespace internal |