Squashed 'third_party/ceres/' content from commit e51e9b4
Change-Id: I763587619d57e594d3fa158dc3a7fe0b89a1743b
git-subtree-dir: third_party/ceres
git-subtree-split: e51e9b46f6ca88ab8b2266d0e362771db6d98067
diff --git a/internal/ceres/line_search.h b/internal/ceres/line_search.h
new file mode 100644
index 0000000..a162979
--- /dev/null
+++ b/internal/ceres/line_search.h
@@ -0,0 +1,307 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2015 Google Inc. All rights reserved.
+// http://ceres-solver.org/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+// POSSIBILITY OF SUCH DAMAGE.
+//
+// Author: sameeragarwal@google.com (Sameer Agarwal)
+//
+// Interface for and implementation of various Line search algorithms.
+
+#ifndef CERES_INTERNAL_LINE_SEARCH_H_
+#define CERES_INTERNAL_LINE_SEARCH_H_
+
+#include <string>
+#include <vector>
+#include "ceres/function_sample.h"
+#include "ceres/internal/eigen.h"
+#include "ceres/internal/port.h"
+#include "ceres/types.h"
+
+namespace ceres {
+namespace internal {
+
+class Evaluator;
+class LineSearchFunction;
+
+// Line search is another name for a one dimensional optimization
+// algorithm. The name "line search" comes from the fact one
+// dimensional optimization problems that arise as subproblems of
+// general multidimensional optimization problems.
+//
+// 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
+// algorithms, e.g., Armijo, Wolfe etc.
+class LineSearch {
+ public:
+ struct Summary;
+
+ struct Options {
+ // Degree of the polynomial used to approximate the objective
+ // function.
+ LineSearchInterpolationType interpolation_type = CUBIC;
+
+ // Armijo and Wolfe 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 sufficient_decrease = 1e-4;
+
+ // In each iteration of the Armijo / Wolfe line search,
+ //
+ // new_step_size >= max_step_contraction * step_size
+ //
+ // Note that by definition, for contraction:
+ //
+ // 0 < max_step_contraction < min_step_contraction < 1
+ //
+ double max_step_contraction = 1e-3;
+
+ // In each iteration of the Armijo / Wolfe line search,
+ //
+ // new_step_size <= min_step_contraction * step_size
+ // Note that by definition, for contraction:
+ //
+ // 0 < max_step_contraction < min_step_contraction < 1
+ //
+ 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 = 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 = 20;
+
+ // Wolfe-specific line search parameters.
+
+ // The strong Wolfe conditions consist of the Armijo sufficient
+ // decrease condition, and an additional requirement that the
+ // step-size be chosen s.t. the _magnitude_ ('strong' Wolfe
+ // conditions) of the gradient along the search direction
+ // decreases sufficiently. Precisely, this second condition
+ // is that we seek a step_size s.t.
+ //
+ // |f'(step_size)| <= sufficient_curvature_decrease * |f'(0)|
+ //
+ // 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 = 0.9;
+
+ // During the bracketing phase of the Wolfe search, the step size is
+ // increased until either a point satisfying the Wolfe conditions is
+ // found, or an upper bound for a bracket containing a point satisfying
+ // the conditions is found. Precisely, at each iteration of the
+ // expansion:
+ //
+ // new_step_size <= max_step_expansion * step_size.
+ //
+ // By definition for expansion, max_step_expansion > 1.0.
+ double max_step_expansion = 10;
+
+ bool is_silent = false;
+
+ // The one dimensional function that the line search algorithm
+ // minimizes.
+ LineSearchFunction* function = nullptr;
+ };
+
+ // Result of the line search.
+ struct Summary {
+ 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 = 0.0;
+ // Cumulative time spent evaluating the gradient of the cost function across
+ // all iterations.
+ 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 = 0.0;
+ double total_time_in_seconds = 0.0;
+ std::string error;
+ };
+
+ explicit LineSearch(const LineSearch::Options& options);
+ virtual ~LineSearch() {}
+
+ static LineSearch* Create(const LineSearchType line_search_type,
+ const LineSearch::Options& options,
+ std::string* error);
+
+ // Perform the line search.
+ //
+ // step_size_estimate must be a positive number.
+ //
+ // initial_cost and initial_gradient are the values and gradient of
+ // the function at zero.
+ // summary must not be null and will contain the result of the line
+ // search.
+ //
+ // Summary::success is true if a non-zero step size is found.
+ void Search(double step_size_estimate,
+ double initial_cost,
+ double initial_gradient,
+ Summary* summary) const;
+ double InterpolatingPolynomialMinimizingStepSize(
+ const LineSearchInterpolationType& interpolation_type,
+ const FunctionSample& lowerbound_sample,
+ const FunctionSample& previous_sample,
+ const FunctionSample& current_sample,
+ const double min_step_size,
+ const double max_step_size) const;
+
+ protected:
+ const LineSearch::Options& options() const { return options_; }
+
+ private:
+ virtual void DoSearch(double step_size_estimate,
+ double initial_cost,
+ double initial_gradient,
+ Summary* summary) const = 0;
+
+ private:
+ LineSearch::Options options_;
+};
+
+// An object used by the line search to access the function values
+// and gradient of the one dimensional function being optimized.
+//
+// In practice, this object provides access to the objective
+// function value and the directional derivative of the underlying
+// optimization problem along a specific search direction.
+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)
+ //
+ // Where, p is the objective function of the general optimization
+ // problem.
+ //
+ // evaluate_gradient controls whether the gradient will be evaluated
+ // or not.
+ //
+ // 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_;
+
+ // scaled_direction = x * direction_;
+ Vector scaled_direction_;
+
+ // 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
+ // value & gradient to accurately determine the duration of the evaluations
+ // we invoked. These are reset by a call to ResetTimeStatistics().
+ double initial_evaluator_residual_time_in_seconds;
+ double initial_evaluator_jacobian_time_in_seconds;
+};
+
+// Backtracking and interpolation based Armijo line search. This
+// implementation is based on the Armijo line search that ships in the
+// minFunc package by Mark Schmidt.
+//
+// For more details: http://www.di.ens.fr/~mschmidt/Software/minFunc.html
+class ArmijoLineSearch : public LineSearch {
+ public:
+ explicit ArmijoLineSearch(const LineSearch::Options& options);
+ virtual ~ArmijoLineSearch() {}
+
+ private:
+ virtual void DoSearch(double step_size_estimate,
+ double initial_cost,
+ double initial_gradient,
+ Summary* summary) const;
+};
+
+// Bracketing / Zoom Strong Wolfe condition line search. This implementation
+// is based on the pseudo-code algorithm presented in Nocedal & Wright [1]
+// (p60-61) with inspiration from the WolfeLineSearch which ships with the
+// minFunc package by Mark Schmidt [2].
+//
+// [1] Nocedal J., Wright S., Numerical Optimization, 2nd Ed., Springer, 1999.
+// [2] http://www.di.ens.fr/~mschmidt/Software/minFunc.html.
+class WolfeLineSearch : public LineSearch {
+ public:
+ explicit WolfeLineSearch(const LineSearch::Options& options);
+ virtual ~WolfeLineSearch() {}
+
+ // Returns true iff either a valid point, or valid bracket are found.
+ bool BracketingPhase(const FunctionSample& initial_position,
+ const double step_size_estimate,
+ FunctionSample* bracket_low,
+ FunctionSample* bracket_high,
+ bool* perform_zoom_search,
+ Summary* summary) const;
+ // Returns true iff final_line_sample satisfies strong Wolfe conditions.
+ bool ZoomPhase(const FunctionSample& initial_position,
+ FunctionSample bracket_low,
+ FunctionSample bracket_high,
+ FunctionSample* solution,
+ Summary* summary) const;
+
+ private:
+ virtual void DoSearch(double step_size_estimate,
+ double initial_cost,
+ double initial_gradient,
+ Summary* summary) const;
+};
+
+} // namespace internal
+} // namespace ceres
+
+#endif // CERES_INTERNAL_LINE_SEARCH_H_