// 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)
#ifndef CERES_PUBLIC_GRADIENT_PROBLEM_SOLVER_H_
#define CERES_PUBLIC_GRADIENT_PROBLEM_SOLVER_H_
#include <cmath>
#include <string>
#include <vector>
#include "ceres/internal/macros.h"
#include "ceres/internal/port.h"
#include "ceres/iteration_callback.h"
#include "ceres/types.h"
#include "ceres/internal/disable_warnings.h"
namespace ceres {
class GradientProblem;
class CERES_EXPORT GradientProblemSolver {
public:
virtual ~GradientProblemSolver();
// The options structure contains, not surprisingly, options that control how
// the solver operates. The defaults should be suitable for a wide range of
// problems; however, better performance is often obtainable with tweaking.
//
// The constants are defined inside types.h
struct CERES_EXPORT Options {
// Default constructor that sets up a generic sparse problem.
Options() {
line_search_direction_type = LBFGS;
line_search_type = WOLFE;
nonlinear_conjugate_gradient_type = FLETCHER_REEVES;
max_lbfgs_rank = 20;
use_approximate_eigenvalue_bfgs_scaling = false;
line_search_interpolation_type = CUBIC;
min_line_search_step_size = 1e-9;
line_search_sufficient_function_decrease = 1e-4;
max_line_search_step_contraction = 1e-3;
min_line_search_step_contraction = 0.6;
max_num_line_search_step_size_iterations = 20;
max_num_line_search_direction_restarts = 5;
line_search_sufficient_curvature_decrease = 0.9;
max_line_search_step_expansion = 10.0;
max_num_iterations = 50;
max_solver_time_in_seconds = 1e9;
function_tolerance = 1e-6;
gradient_tolerance = 1e-10;
parameter_tolerance = 1e-8;
logging_type = PER_MINIMIZER_ITERATION;
minimizer_progress_to_stdout = false;
}
// Returns true if the options struct has a valid
// configuration. Returns false otherwise, and fills in *error
// with a message describing the problem.
bool IsValid(std::string* error) const;
// Minimizer options ----------------------------------------
LineSearchDirectionType line_search_direction_type;
LineSearchType line_search_type;
NonlinearConjugateGradientType nonlinear_conjugate_gradient_type;
// The LBFGS hessian approximation is a low rank approximation to
// the inverse of the Hessian matrix. The rank of the
// approximation determines (linearly) the space and time
// complexity of using the approximation. Higher the rank, the
// better is the quality of the approximation. The increase in
// quality is however is bounded for a number of reasons.
//
// 1. The method only uses secant information and not actual
// derivatives.
//
// 2. The Hessian approximation is constrained to be positive
// definite.
//
// So increasing this rank to a large number will cost time and
// space complexity without the corresponding increase in solution
// quality. There are no hard and fast rules for choosing the
// maximum rank. The best choice usually requires some problem
// specific experimentation.
//
// For more theoretical and implementation details of the LBFGS
// method, please see:
//
// Nocedal, J. (1980). "Updating Quasi-Newton Matrices with
// Limited Storage". Mathematics of Computation 35 (151): 773–782.
int max_lbfgs_rank;
// As part of the (L)BFGS update step (BFGS) / right-multiply step (L-BFGS),
// the initial inverse Hessian approximation is taken to be the Identity.
// However, Oren showed that using instead I * \gamma, where \gamma is
// chosen to approximate an eigenvalue of the true inverse Hessian can
// result in improved convergence in a wide variety of cases. Setting
// use_approximate_eigenvalue_bfgs_scaling to true enables this scaling.
//
// It is important to note that approximate eigenvalue scaling does not
// always improve convergence, and that it can in fact significantly degrade
// performance for certain classes of problem, which is why it is disabled
// by default. In particular it can degrade performance when the
// sensitivity of the problem to different parameters varies significantly,
// as in this case a single scalar factor fails to capture this variation
// and detrimentally downscales parts of the jacobian approximation which
// correspond to low-sensitivity parameters. It can also reduce the
// robustness of the solution to errors in the jacobians.
//
// Oren S.S., Self-scaling variable metric (SSVM) algorithms
// Part II: Implementation and experiments, Management Science,
// 20(5), 863-874, 1974.
bool use_approximate_eigenvalue_bfgs_scaling;
// 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;
// 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 line_search_sufficient_function_decrease;
// In each iteration of the line search,
//
// new_step_size >= max_line_search_step_contraction * step_size
//
// Note that by definition, for contraction:
//
// 0 < max_step_contraction < min_step_contraction < 1
//
double max_line_search_step_contraction;
// In each iteration of the line search,
//
// new_step_size <= min_line_search_step_contraction * step_size
//
// Note that by definition, for contraction:
//
// 0 < max_step_contraction < min_step_contraction < 1
//
double min_line_search_step_contraction;
// 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_line_search_step_size_iterations;
// Maximum number of restarts of the line search direction algorithm before
// terminating the optimization. Restarts of the line search direction
// algorithm occur when the current algorithm fails to produce a new descent
// direction. This typically indicates a numerical failure, or a breakdown
// in the validity of the approximations used.
int max_num_line_search_direction_restarts;
// 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 line_search_sufficient_curvature_decrease;
// 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_line_search_step_expansion;
// Maximum number of iterations for the minimizer to run for.
int max_num_iterations;
// Maximum time for which the minimizer should run for.
double max_solver_time_in_seconds;
// Minimizer terminates when
//
// (new_cost - old_cost) < function_tolerance * old_cost;
//
double function_tolerance;
// Minimizer terminates when
//
// max_i |x - Project(Plus(x, -g(x))| < gradient_tolerance
//
// This value should typically be 1e-4 * function_tolerance.
double gradient_tolerance;
// Minimizer terminates when
//
// |step|_2 <= parameter_tolerance * ( |x|_2 + parameter_tolerance)
//
double parameter_tolerance;
// Logging options ---------------------------------------------------------
LoggingType logging_type;
// By default the Minimizer progress is logged to VLOG(1), which
// is sent to STDERR depending on the vlog level. If this flag is
// set to true, and logging_type is not SILENT, the logging output
// is sent to STDOUT.
bool minimizer_progress_to_stdout;
// Callbacks that are executed at the end of each iteration of the
// Minimizer. An iteration may terminate midway, either due to
// numerical failures or because one of the convergence tests has
// been satisfied. In this case none of the callbacks are
// executed.
// Callbacks are executed in the order that they are specified in
// this vector. By default, parameter blocks are updated only at
// the end of the optimization, i.e when the Minimizer
// terminates. This behaviour is controlled by
// update_state_every_variable. If the user wishes to have access
// to the update parameter blocks when his/her callbacks are
// executed, then set update_state_every_iteration to true.
//
// The solver does NOT take ownership of these pointers.
std::vector<IterationCallback*> callbacks;
};
struct CERES_EXPORT Summary {
Summary();
// A brief one line description of the state of the solver after
// termination.
std::string BriefReport() const;
// A full multiline description of the state of the solver after
// termination.
std::string FullReport() const;
bool IsSolutionUsable() const;
// Minimizer summary -------------------------------------------------
TerminationType termination_type;
// Reason why the solver terminated.
std::string message;
// Cost of the problem (value of the objective function) before
// the optimization.
double initial_cost;
// Cost of the problem (value of the objective function) after the
// optimization.
double final_cost;
// IterationSummary for each minimizer iteration in order.
std::vector<IterationSummary> iterations;
// Number of times the cost (and not the gradient) was evaluated.
int num_cost_evaluations;
// Number of times the gradient (and the cost) were evaluated.
int num_gradient_evaluations;
// Sum total of all time spent inside Ceres when Solve is called.
double total_time_in_seconds;
// Time (in seconds) spent evaluating the cost.
double cost_evaluation_time_in_seconds;
// Time (in seconds) spent evaluating the gradient.
double gradient_evaluation_time_in_seconds;
// Time (in seconds) spent minimizing the interpolating polynomial
// to compute the next candidate step size as part of a line search.
double line_search_polynomial_minimization_time_in_seconds;
// Number of parameters in the probem.
int num_parameters;
// Dimension of the tangent space of the problem.
int num_local_parameters;
// Type of line search direction used.
LineSearchDirectionType line_search_direction_type;
// Type of the line search algorithm used.
LineSearchType line_search_type;
// When performing line search, the degree of the polynomial used
// to approximate the objective function.
LineSearchInterpolationType line_search_interpolation_type;
// If the line search direction is NONLINEAR_CONJUGATE_GRADIENT,
// then this indicates the particular variant of non-linear
// conjugate gradient used.
NonlinearConjugateGradientType nonlinear_conjugate_gradient_type;
// If the type of the line search direction is LBFGS, then this
// indicates the rank of the Hessian approximation.
int max_lbfgs_rank;
};
// Once a least squares problem has been built, this function takes
// the problem and optimizes it based on the values of the options
// parameters. Upon return, a detailed summary of the work performed
// by the preprocessor, the non-linear minmizer and the linear
// solver are reported in the summary object.
virtual void Solve(const GradientProblemSolver::Options& options,
const GradientProblem& problem,
double* parameters,
GradientProblemSolver::Summary* summary);
};
// Helper function which avoids going through the interface.
CERES_EXPORT void Solve(const GradientProblemSolver::Options& options,
const GradientProblem& problem,
double* parameters,
GradientProblemSolver::Summary* summary);
} // namespace ceres
#include "ceres/internal/reenable_warnings.h"
#endif // CERES_PUBLIC_GRADIENT_PROBLEM_SOLVER_H_