// 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_