Compute & report timing information for line searches.
- We now compute & report the cumulative time spent performing the
following tasks as part of a line search:
- Evaluation of the univariate cost function value & gradient.
- Minimization of the interpolating polynomial.
- Total time spent performing line searches.
- This information is now reported for all minimizers, although only in
the case of a constrained problem for the TR minimizer.
- Remove LineSearch::Function abstraction in place of using
LineSearchFunction implementation directly, and remove virtual
functions from LineSearchFunction.
-- LineSearch::Function added an unnecessary level of abstraction since
the user always had to create a LineSearchFunction anyway to use a
Ceres Evaluator, and it added an unncessary virtual function call.
Change-Id: Ia4e1921d78f351ae119875aa97a3ea5e8b5d9877
diff --git a/internal/ceres/line_search.h b/internal/ceres/line_search.h
index 97b9bc6..ea72f74 100644
--- a/internal/ceres/line_search.h
+++ b/internal/ceres/line_search.h
@@ -44,6 +44,7 @@
class Evaluator;
struct FunctionSample;
+class LineSearchFunction;
// Line search is another name for a one dimensional optimization
// algorithm. The name "line search" comes from the fact one
@@ -57,7 +58,7 @@
// algorithms, e.g., Armijo, Wolfe etc.
class LineSearch {
public:
- class Function;
+ struct Summary;
struct Options {
Options()
@@ -147,31 +148,7 @@
// The one dimensional function that the line search algorithm
// minimizes.
- Function* function;
- };
-
- // 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 will provide access to the objective
- // function value and the directional derivative of the underlying
- // optimization problem along a specific search direction.
- //
- // See LineSearchFunction for an example implementation.
- class Function {
- public:
- virtual ~Function() {}
- // Evaluate the line search objective
- //
- // f(x) = p(position + x * direction)
- //
- // Where, p is the objective function of the general optimization
- // problem.
- //
- // g is the gradient f'(x) at x.
- //
- // f must not be null. The gradient is computed only if g is not null.
- virtual bool Evaluate(double x, double* f, double* g) = 0;
+ LineSearchFunction* function;
};
// Result of the line search.
@@ -181,13 +158,27 @@
optimal_step_size(0.0),
num_function_evaluations(0),
num_gradient_evaluations(0),
- num_iterations(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;
+ // Cumulative time spent evaluating the value of the cost function across
+ // all iterations.
+ double cost_evaluation_time_in_seconds;
+ // Cumulative time spent evaluating the gradient of the cost function across
+ // all iterations.
+ double gradient_evaluation_time_in_seconds;
+ // 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;
string error;
};
@@ -208,10 +199,10 @@
// search.
//
// Summary::success is true if a non-zero step size is found.
- virtual void Search(double step_size_estimate,
- double initial_cost,
- double initial_gradient,
- Summary* summary) = 0;
+ 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,
@@ -224,16 +215,41 @@
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_;
};
-class LineSearchFunction : public LineSearch::Function {
+// 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);
- virtual ~LineSearchFunction() {}
void Init(const Vector& position, const Vector& direction);
- virtual bool Evaluate(double x, double* f, double* g);
+ // Evaluate the line search objective
+ //
+ // f(x) = p(position + x * direction)
+ //
+ // Where, p is the objective function of the general optimization
+ // problem.
+ //
+ // g is the gradient f'(x) at x.
+ //
+ // f must not be null. The gradient is computed only if g is not null.
+ bool Evaluate(double x, double* f, double* g);
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;
private:
Evaluator* evaluator_;
@@ -246,6 +262,13 @@
// 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
+ // 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
@@ -257,10 +280,12 @@
public:
explicit ArmijoLineSearch(const LineSearch::Options& options);
virtual ~ArmijoLineSearch() {}
- virtual void Search(double step_size_estimate,
- double initial_cost,
- double initial_gradient,
- Summary* summary);
+
+ 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
@@ -274,23 +299,26 @@
public:
explicit WolfeLineSearch(const LineSearch::Options& options);
virtual ~WolfeLineSearch() {}
- virtual void Search(double step_size_estimate,
- double initial_cost,
- double initial_gradient,
- Summary* summary);
+
// 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);
+ 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);
+ Summary* summary) const;
+
+ private:
+ virtual void DoSearch(double step_size_estimate,
+ double initial_cost,
+ double initial_gradient,
+ Summary* summary) const;
};
} // namespace internal
