10ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Ceres Solver - A fast non-linear least squares minimizer
279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// Copyright 2014 Google Inc. All rights reserved.
30ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// http://code.google.com/p/ceres-solver/
40ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong//
50ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Redistribution and use in source and binary forms, with or without
60ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// modification, are permitted provided that the following conditions are met:
70ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong//
80ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Redistributions of source code must retain the above copyright notice,
90ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong//   this list of conditions and the following disclaimer.
100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Redistributions in binary form must reproduce the above copyright notice,
110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong//   this list of conditions and the following disclaimer in the documentation
120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong//   and/or other materials provided with the distribution.
130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Neither the name of Google Inc. nor the names of its contributors may be
140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong//   used to endorse or promote products derived from this software without
150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong//   specific prior written permission.
160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong//
170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// POSSIBILITY OF SUCH DAMAGE.
280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong//
290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Author: sameeragarwal@google.com (Sameer Agarwal)
300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#ifndef CERES_PUBLIC_SOLVER_H_
320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#define CERES_PUBLIC_SOLVER_H_
330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include <cmath>
350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include <string>
360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include <vector>
370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/crs_matrix.h"
380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/internal/macros.h"
390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/internal/port.h"
400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/iteration_callback.h"
410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/ordered_groups.h"
420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/types.h"
4379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez#include "ceres/internal/disable_warnings.h"
440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongnamespace ceres {
460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongclass Problem;
480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Interface for non-linear least squares solvers.
5079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandezclass CERES_EXPORT Solver {
510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong public:
520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong  virtual ~Solver();
530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong  // The options structure contains, not surprisingly, options that control how
550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong  // the solver operates. The defaults should be suitable for a wide range of
560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong  // problems; however, better performance is often obtainable with tweaking.
570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong  //
580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong  // The constants are defined inside types.h
5979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez  struct CERES_EXPORT Options {
600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Default constructor that sets up a generic sparse problem.
610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    Options() {
621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      minimizer_type = TRUST_REGION;
631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      line_search_direction_type = LBFGS;
641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      line_search_type = WOLFE;
651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      nonlinear_conjugate_gradient_type = FLETCHER_REEVES;
661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      max_lbfgs_rank = 20;
671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      use_approximate_eigenvalue_bfgs_scaling = false;
681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      line_search_interpolation_type = CUBIC;
691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      min_line_search_step_size = 1e-9;
701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      line_search_sufficient_function_decrease = 1e-4;
711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      max_line_search_step_contraction = 1e-3;
721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      min_line_search_step_contraction = 0.6;
731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      max_num_line_search_step_size_iterations = 20;
741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      max_num_line_search_direction_restarts = 5;
751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      line_search_sufficient_curvature_decrease = 0.9;
761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      max_line_search_step_expansion = 10.0;
770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      trust_region_strategy_type = LEVENBERG_MARQUARDT;
780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      dogleg_type = TRADITIONAL_DOGLEG;
790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      use_nonmonotonic_steps = false;
800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      max_consecutive_nonmonotonic_steps = 5;
810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      max_num_iterations = 50;
820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      max_solver_time_in_seconds = 1e9;
830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      num_threads = 1;
840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      initial_trust_region_radius = 1e4;
850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      max_trust_region_radius = 1e16;
860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      min_trust_region_radius = 1e-32;
870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      min_relative_decrease = 1e-3;
881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      min_lm_diagonal = 1e-6;
891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      max_lm_diagonal = 1e32;
900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      max_num_consecutive_invalid_steps = 5;
910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      function_tolerance = 1e-6;
920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      gradient_tolerance = 1e-10;
930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      parameter_tolerance = 1e-8;
940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
9579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez#if defined(CERES_NO_SUITESPARSE) && defined(CERES_NO_CXSPARSE) && !defined(CERES_ENABLE_LGPL_CODE)
960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      linear_solver_type = DENSE_QR;
970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#else
980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      linear_solver_type = SPARSE_NORMAL_CHOLESKY;
990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#endif
1000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
1010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      preconditioner_type = JACOBI;
10279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez      visibility_clustering_type = CANONICAL_VIEWS;
103399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger      dense_linear_algebra_library_type = EIGEN;
10479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
10579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez      // Choose a default sparse linear algebra library in the order:
10679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez      //
10779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez      //   SUITE_SPARSE > CX_SPARSE > EIGEN_SPARSE
10879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez#if !defined(CERES_NO_SUITESPARSE)
109399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger      sparse_linear_algebra_library_type = SUITE_SPARSE;
11079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez#else
11179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez  #if !defined(CERES_NO_CXSPARSE)
112399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger      sparse_linear_algebra_library_type = CX_SPARSE;
11379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez  #else
11479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    #if defined(CERES_USE_EIGEN_SPARSE)
11579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez      sparse_linear_algebra_library_type = EIGEN_SPARSE;
11679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    #endif
11779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez  #endif
1180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#endif
1190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
1200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      num_linear_solver_threads = 1;
1211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      use_postordering = false;
12279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez      dynamic_sparsity = false;
1231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      min_linear_solver_iterations = 1;
1241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      max_linear_solver_iterations = 500;
1250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      eta = 1e-1;
1260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      jacobi_scaling = true;
1271d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      use_inner_iterations = false;
1281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      inner_iteration_tolerance = 1e-3;
1290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      logging_type = PER_MINIMIZER_ITERATION;
1300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      minimizer_progress_to_stdout = false;
1311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      trust_region_problem_dump_directory = "/tmp";
1321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling      trust_region_problem_dump_format_type = TEXTFILE;
1330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      check_gradients = false;
1340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      gradient_check_relative_precision = 1e-8;
1350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      numeric_derivative_relative_step_size = 1e-6;
1360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong      update_state_every_iteration = false;
1370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    }
1380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
13979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Returns true if the options struct has a valid
14079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // configuration. Returns false otherwise, and fills in *error
14179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // with a message describing the problem.
14279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    bool IsValid(string* error) const;
14379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
1440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Minimizer options ----------------------------------------
1450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
1461d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Ceres supports the two major families of optimization strategies -
1471d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Trust Region and Line Search.
1481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
1491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // 1. The line search approach first finds a descent direction
1501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // along which the objective function will be reduced and then
1511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // computes a step size that decides how far should move along
1521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // that direction. The descent direction can be computed by
1531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // various methods, such as gradient descent, Newton's method and
1541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Quasi-Newton method. The step size can be determined either
1551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // exactly or inexactly.
1561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
1571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // 2. The trust region approach approximates the objective
1581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // function using using a model function (often a quadratic) over
1591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // a subset of the search space known as the trust region. If the
1601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // model function succeeds in minimizing the true objective
1611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // function the trust region is expanded; conversely, otherwise it
1621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // is contracted and the model optimization problem is solved
1631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // again.
1641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
1651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Trust region methods are in some sense dual to line search methods:
1661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // trust region methods first choose a step size (the size of the
1671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // trust region) and then a step direction while line search methods
1681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // first choose a step direction and then a step size.
1691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    MinimizerType minimizer_type;
1701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
1711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    LineSearchDirectionType line_search_direction_type;
1721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    LineSearchType line_search_type;
1731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    NonlinearConjugateGradientType nonlinear_conjugate_gradient_type;
1741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
1751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // The LBFGS hessian approximation is a low rank approximation to
1761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // the inverse of the Hessian matrix. The rank of the
1771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // approximation determines (linearly) the space and time
1781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // complexity of using the approximation. Higher the rank, the
1791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // better is the quality of the approximation. The increase in
1801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // quality is however is bounded for a number of reasons.
1811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
1821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // 1. The method only uses secant information and not actual
1831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // derivatives.
1841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
1851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // 2. The Hessian approximation is constrained to be positive
1861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // definite.
1871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
1881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // So increasing this rank to a large number will cost time and
1891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // space complexity without the corresponding increase in solution
1901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // quality. There are no hard and fast rules for choosing the
1911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // maximum rank. The best choice usually requires some problem
1921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // specific experimentation.
1931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
1941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // For more theoretical and implementation details of the LBFGS
1951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // method, please see:
1961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
1971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Nocedal, J. (1980). "Updating Quasi-Newton Matrices with
1981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Limited Storage". Mathematics of Computation 35 (151): 773–782.
1991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    int max_lbfgs_rank;
2001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
2011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // As part of the (L)BFGS update step (BFGS) / right-multiply step (L-BFGS),
2021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // the initial inverse Hessian approximation is taken to be the Identity.
2031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // However, Oren showed that using instead I * \gamma, where \gamma is
2041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // chosen to approximate an eigenvalue of the true inverse Hessian can
2051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // result in improved convergence in a wide variety of cases. Setting
2061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // use_approximate_eigenvalue_bfgs_scaling to true enables this scaling.
2071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
2081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // It is important to note that approximate eigenvalue scaling does not
2091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // always improve convergence, and that it can in fact significantly degrade
2101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // performance for certain classes of problem, which is why it is disabled
2111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // by default.  In particular it can degrade performance when the
2121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // sensitivity of the problem to different parameters varies significantly,
2131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // as in this case a single scalar factor fails to capture this variation
2141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // and detrimentally downscales parts of the jacobian approximation which
2151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // correspond to low-sensitivity parameters. It can also reduce the
2161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // robustness of the solution to errors in the jacobians.
2171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
2181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Oren S.S., Self-scaling variable metric (SSVM) algorithms
2191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Part II: Implementation and experiments, Management Science,
2201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // 20(5), 863-874, 1974.
2211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    bool use_approximate_eigenvalue_bfgs_scaling;
2221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
2231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Degree of the polynomial used to approximate the objective
2241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // function. Valid values are BISECTION, QUADRATIC and CUBIC.
2251d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
2261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // BISECTION corresponds to pure backtracking search with no
2271d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // interpolation.
2281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    LineSearchInterpolationType line_search_interpolation_type;
2291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
2301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // If during the line search, the step_size falls below this
2311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // value, it is truncated to zero.
2321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    double min_line_search_step_size;
2331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
2341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Line search parameters.
2351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
2361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Solving the line search problem exactly is computationally
2371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // prohibitive. Fortunately, line search based optimization
2381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // algorithms can still guarantee convergence if instead of an
2391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // exact solution, the line search algorithm returns a solution
2401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // which decreases the value of the objective function
2411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // sufficiently. More precisely, we are looking for a step_size
2421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // s.t.
2431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
2441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //   f(step_size) <= f(0) + sufficient_decrease * f'(0) * step_size
2451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
2461d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    double line_search_sufficient_function_decrease;
2471d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
2481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // In each iteration of the line search,
2491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
2501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //  new_step_size >= max_line_search_step_contraction * step_size
2511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
2521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Note that by definition, for contraction:
2531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
2541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //  0 < max_step_contraction < min_step_contraction < 1
2551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
2561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    double max_line_search_step_contraction;
2571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
2581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // In each iteration of the line search,
2591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
2601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //  new_step_size <= min_line_search_step_contraction * step_size
2611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
2621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Note that by definition, for contraction:
2631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
2641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //  0 < max_step_contraction < min_step_contraction < 1
2651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
2661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    double min_line_search_step_contraction;
2671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
2681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Maximum number of trial step size iterations during each line search,
2691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // if a step size satisfying the search conditions cannot be found within
2701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // this number of trials, the line search will terminate.
2711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    int max_num_line_search_step_size_iterations;
2721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
2731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Maximum number of restarts of the line search direction algorithm before
2741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // terminating the optimization. Restarts of the line search direction
2751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // algorithm occur when the current algorithm fails to produce a new descent
2761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // direction. This typically indicates a numerical failure, or a breakdown
2771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // in the validity of the approximations used.
2781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    int max_num_line_search_direction_restarts;
2791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
2801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // The strong Wolfe conditions consist of the Armijo sufficient
2811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // decrease condition, and an additional requirement that the
2821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // step-size be chosen s.t. the _magnitude_ ('strong' Wolfe
2831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // conditions) of the gradient along the search direction
2841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // decreases sufficiently. Precisely, this second condition
2851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // is that we seek a step_size s.t.
2861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
2871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //   |f'(step_size)| <= sufficient_curvature_decrease * |f'(0)|
2881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
2891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Where f() is the line search objective and f'() is the derivative
2901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // of f w.r.t step_size (d f / d step_size).
2911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    double line_search_sufficient_curvature_decrease;
2921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
2931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // During the bracketing phase of the Wolfe search, the step size is
2941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // increased until either a point satisfying the Wolfe conditions is
2951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // found, or an upper bound for a bracket containing a point satisfying
2961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // the conditions is found.  Precisely, at each iteration of the
2971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // expansion:
2981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
2991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //   new_step_size <= max_step_expansion * step_size.
3001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
3011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // By definition for expansion, max_step_expansion > 1.0.
3021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    double max_line_search_step_expansion;
3031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
3040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    TrustRegionStrategyType trust_region_strategy_type;
3050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
3060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Type of dogleg strategy to use.
3070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    DoglegType dogleg_type;
3080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
3090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // The classical trust region methods are descent methods, in that
3100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // they only accept a point if it strictly reduces the value of
3110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // the objective function.
3120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
3130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Relaxing this requirement allows the algorithm to be more
3140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // efficient in the long term at the cost of some local increase
3150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // in the value of the objective function.
3160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
3170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // This is because allowing for non-decreasing objective function
3180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // values in a princpled manner allows the algorithm to "jump over
3190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // boulders" as the method is not restricted to move into narrow
3200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // valleys while preserving its convergence properties.
3210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
3220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Setting use_nonmonotonic_steps to true enables the
3230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // non-monotonic trust region algorithm as described by Conn,
3240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Gould & Toint in "Trust Region Methods", Section 10.1.
3250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
3260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // The parameter max_consecutive_nonmonotonic_steps controls the
3270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // window size used by the step selection algorithm to accept
3280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // non-monotonic steps.
3290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
3300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Even though the value of the objective function may be larger
3310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // than the minimum value encountered over the course of the
3320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // optimization, the final parameters returned to the user are the
3330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // ones corresponding to the minimum cost over all iterations.
3340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    bool use_nonmonotonic_steps;
3350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    int max_consecutive_nonmonotonic_steps;
3360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
3370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Maximum number of iterations for the minimizer to run for.
3380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    int max_num_iterations;
3390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
3400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Maximum time for which the minimizer should run for.
3410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    double max_solver_time_in_seconds;
3420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
3430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Number of threads used by Ceres for evaluating the cost and
3440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // jacobians.
3450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    int num_threads;
3460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
3470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Trust region minimizer settings.
3480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    double initial_trust_region_radius;
3490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    double max_trust_region_radius;
3500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
3510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Minimizer terminates when the trust region radius becomes
3520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // smaller than this value.
3530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    double min_trust_region_radius;
3540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
3550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Lower bound for the relative decrease before a step is
3560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // accepted.
3570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    double min_relative_decrease;
3580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
3590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // For the Levenberg-Marquadt algorithm, the scaled diagonal of
3600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // the normal equations J'J is used to control the size of the
3610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // trust region. Extremely small and large values along the
3620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // diagonal can make this regularization scheme
3631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // fail. max_lm_diagonal and min_lm_diagonal, clamp the values of
3640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // diag(J'J) from above and below. In the normal course of
3650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // operation, the user should not have to modify these parameters.
3661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    double min_lm_diagonal;
3671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    double max_lm_diagonal;
3680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
3690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Sometimes due to numerical conditioning problems or linear
3700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // solver flakiness, the trust region strategy may return a
3710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // numerically invalid step that can be fixed by reducing the
3720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // trust region size. So the TrustRegionMinimizer allows for a few
3730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // successive invalid steps before it declares NUMERICAL_FAILURE.
3740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    int max_num_consecutive_invalid_steps;
3750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
3760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Minimizer terminates when
3770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
3780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //   (new_cost - old_cost) < function_tolerance * old_cost;
3790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
3800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    double function_tolerance;
3810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
3820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Minimizer terminates when
3830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
38479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    //   max_i |x - Project(Plus(x, -g(x))| < gradient_tolerance
3850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
3860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // This value should typically be 1e-4 * function_tolerance.
3870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    double gradient_tolerance;
3880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
3890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Minimizer terminates when
3900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
3910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //   |step|_2 <= parameter_tolerance * ( |x|_2 +  parameter_tolerance)
3920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
3930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    double parameter_tolerance;
3940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
3950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Linear least squares solver options -------------------------------------
3960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
3970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    LinearSolverType linear_solver_type;
3980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
3990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Type of preconditioner to use with the iterative linear solvers.
4000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    PreconditionerType preconditioner_type;
4010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
40279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Type of clustering algorithm to use for visibility based
40379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // preconditioning. This option is used only when the
40479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // preconditioner_type is CLUSTER_JACOBI or CLUSTER_TRIDIAGONAL.
40579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    VisibilityClusteringType visibility_clustering_type;
40679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
407399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger    // Ceres supports using multiple dense linear algebra libraries
408399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger    // for dense matrix factorizations. Currently EIGEN and LAPACK are
409399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger    // the valid choices. EIGEN is always available, LAPACK refers to
410399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger    // the system BLAS + LAPACK library which may or may not be
411399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger    // available.
412399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger    //
413399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger    // This setting affects the DENSE_QR, DENSE_NORMAL_CHOLESKY and
414399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger    // DENSE_SCHUR solvers. For small to moderate sized probem EIGEN
415399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger    // is a fine choice but for large problems, an optimized LAPACK +
416399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger    // BLAS implementation can make a substantial difference in
417399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger    // performance.
418399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger    DenseLinearAlgebraLibraryType dense_linear_algebra_library_type;
419399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger
4200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Ceres supports using multiple sparse linear algebra libraries
4210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // for sparse matrix ordering and factorizations. Currently,
4220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // SUITE_SPARSE and CX_SPARSE are the valid choices, depending on
4230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // whether they are linked into Ceres at build time.
424399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger    SparseLinearAlgebraLibraryType sparse_linear_algebra_library_type;
4250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
4260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Number of threads used by Ceres to solve the Newton
4270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // step. Currently only the SPARSE_SCHUR solver is capable of
4280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // using this setting.
4290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    int num_linear_solver_threads;
4300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
4310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // The order in which variables are eliminated in a linear solver
4320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // can have a significant of impact on the efficiency and accuracy
4330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // of the method. e.g., when doing sparse Cholesky factorization,
4340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // there are matrices for which a good ordering will give a
4350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Cholesky factor with O(n) storage, where as a bad ordering will
4360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // result in an completely dense factor.
4370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
4380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Ceres allows the user to provide varying amounts of hints to
4390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // the solver about the variable elimination ordering to use. This
4400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // can range from no hints, where the solver is free to decide the
4410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // best possible ordering based on the user's choices like the
4420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // linear solver being used, to an exact order in which the
4430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // variables should be eliminated, and a variety of possibilities
4440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // in between.
4450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
4460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Instances of the ParameterBlockOrdering class are used to
4470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // communicate this information to Ceres.
4480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
4490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Formally an ordering is an ordered partitioning of the
4500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // parameter blocks, i.e, each parameter block belongs to exactly
4510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // one group, and each group has a unique non-negative integer
4520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // associated with it, that determines its order in the set of
4530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // groups.
4540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
4550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Given such an ordering, Ceres ensures that the parameter blocks in
4560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // the lowest numbered group are eliminated first, and then the
4570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // parmeter blocks in the next lowest numbered group and so on. Within
4580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // each group, Ceres is free to order the parameter blocks as it
4590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // chooses.
4600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
4610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // If NULL, then all parameter blocks are assumed to be in the
4620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // same group and the solver is free to decide the best
4630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // ordering.
4640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
4650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // e.g. Consider the linear system
4660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
4670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //   x + y = 3
4680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //   2x + 3y = 7
4690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
4700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // There are two ways in which it can be solved. First eliminating x
4710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // from the two equations, solving for y and then back substituting
4720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // for x, or first eliminating y, solving for x and back substituting
4730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // for y. The user can construct three orderings here.
4740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
4750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //   {0: x}, {1: y} - eliminate x first.
4760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //   {0: y}, {1: x} - eliminate y first.
4770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //   {0: x, y}      - Solver gets to decide the elimination order.
4780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
4790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Thus, to have Ceres determine the ordering automatically using
4800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // heuristics, put all the variables in group 0 and to control the
4810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // ordering for every variable, create groups 0..N-1, one per
4820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // variable, in the desired order.
4830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
4840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Bundle Adjustment
4850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // -----------------
4860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
4870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // A particular case of interest is bundle adjustment, where the user
4880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // has two options. The default is to not specify an ordering at all,
4890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // the solver will see that the user wants to use a Schur type solver
4900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // and figure out the right elimination ordering.
4910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
4920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // But if the user already knows what parameter blocks are points and
4930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // what are cameras, they can save preprocessing time by partitioning
4940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // the parameter blocks into two groups, one for the points and one
4950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // for the cameras, where the group containing the points has an id
4960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // smaller than the group containing cameras.
49779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    shared_ptr<ParameterBlockOrdering> linear_solver_ordering;
4980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
4991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Sparse Cholesky factorization algorithms use a fill-reducing
5001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // ordering to permute the columns of the Jacobian matrix. There
5011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // are two ways of doing this.
5021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
5031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // 1. Compute the Jacobian matrix in some order and then have the
5041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //    factorization algorithm permute the columns of the Jacobian.
5051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
5061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // 2. Compute the Jacobian with its columns already permuted.
5071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
5081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // The first option incurs a significant memory penalty. The
5091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // factorization algorithm has to make a copy of the permuted
5101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Jacobian matrix, thus Ceres pre-permutes the columns of the
5111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Jacobian matrix and generally speaking, there is no performance
5121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // penalty for doing so.
5131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
5141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // In some rare cases, it is worth using a more complicated
5151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // reordering algorithm which has slightly better runtime
5161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // performance at the expense of an extra copy of the Jacobian
5171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // matrix. Setting use_postordering to true enables this tradeoff.
5181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    bool use_postordering;
5190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
52079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Some non-linear least squares problems are symbolically dense but
52179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // numerically sparse. i.e. at any given state only a small number
52279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // of jacobian entries are non-zero, but the position and number of
52379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // non-zeros is different depending on the state. For these problems
52479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // it can be useful to factorize the sparse jacobian at each solver
52579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // iteration instead of including all of the zero entries in a single
52679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // general factorization.
52779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    //
52879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // If your problem does not have this property (or you do not know),
52979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // then it is probably best to keep this false, otherwise it will
53079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // likely lead to worse performance.
53179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
53279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // This settings affects the SPARSE_NORMAL_CHOLESKY solver.
53379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    bool dynamic_sparsity;
53479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
5350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Some non-linear least squares problems have additional
5360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // structure in the way the parameter blocks interact that it is
5370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // beneficial to modify the way the trust region step is computed.
5380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
5390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // e.g., consider the following regression problem
5400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
5410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //   y = a_1 exp(b_1 x) + a_2 exp(b_3 x^2 + c_1)
5420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
5430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Given a set of pairs{(x_i, y_i)}, the user wishes to estimate
5440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // a_1, a_2, b_1, b_2, and c_1.
5450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
5460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Notice here that the expression on the left is linear in a_1
5470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // and a_2, and given any value for b_1, b_2 and c_1, it is
5480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // possible to use linear regression to estimate the optimal
5490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // values of a_1 and a_2. Indeed, its possible to analytically
5500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // eliminate the variables a_1 and a_2 from the problem all
5510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // together. Problems like these are known as separable least
5520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // squares problem and the most famous algorithm for solving them
5530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // is the Variable Projection algorithm invented by Golub &
5540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Pereyra.
5550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
5560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Similar structure can be found in the matrix factorization with
5570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // missing data problem. There the corresponding algorithm is
5580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // known as Wiberg's algorithm.
5590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
5600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Ruhe & Wedin (Algorithms for Separable Nonlinear Least Squares
5610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Problems, SIAM Reviews, 22(3), 1980) present an analyis of
5620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // various algorithms for solving separable non-linear least
5630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // squares problems and refer to "Variable Projection" as
5640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Algorithm I in their paper.
5650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
5660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Implementing Variable Projection is tedious and expensive, and
5670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // they present a simpler algorithm, which they refer to as
5680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Algorithm II, where once the Newton/Trust Region step has been
5690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // computed for the whole problem (a_1, a_2, b_1, b_2, c_1) and
5700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // additional optimization step is performed to estimate a_1 and
5710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // a_2 exactly.
5720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
5730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // This idea can be generalized to cases where the residual is not
5740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // linear in a_1 and a_2, i.e., Solve for the trust region step
5750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // for the full problem, and then use it as the starting point to
5760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // further optimize just a_1 and a_2. For the linear case, this
5770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // amounts to doing a single linear least squares solve. For
5780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // non-linear problems, any method for solving the a_1 and a_2
5790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // optimization problems will do. The only constraint on a_1 and
5800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // a_2 is that they do not co-occur in any residual block.
5810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
5820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // This idea can be further generalized, by not just optimizing
5830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // (a_1, a_2), but decomposing the graph corresponding to the
5840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Hessian matrix's sparsity structure in a collection of
5850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // non-overlapping independent sets and optimizing each of them.
5860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
5870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Setting "use_inner_iterations" to true enables the use of this
5880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // non-linear generalization of Ruhe & Wedin's Algorithm II.  This
5890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // version of Ceres has a higher iteration complexity, but also
5900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // displays better convergence behaviour per iteration. Setting
5910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Solver::Options::num_threads to the maximum number possible is
5920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // highly recommended.
5930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    bool use_inner_iterations;
5940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
5950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // If inner_iterations is true, then the user has two choices.
5960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
5970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // 1. Let the solver heuristically decide which parameter blocks
5980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //    to optimize in each inner iteration. To do this leave
5990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //    Solver::Options::inner_iteration_ordering untouched.
6000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
6010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // 2. Specify a collection of of ordered independent sets. Where
6020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //    the lower numbered groups are optimized before the higher
6031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //    number groups. Each group must be an independent set. Not
6041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //    all parameter blocks need to be present in the ordering.
60579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    shared_ptr<ParameterBlockOrdering> inner_iteration_ordering;
6060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
6071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Generally speaking, inner iterations make significant progress
6081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // in the early stages of the solve and then their contribution
6091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // drops down sharply, at which point the time spent doing inner
6101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // iterations is not worth it.
6111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    //
6121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Once the relative decrease in the objective function due to
6131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // inner iterations drops below inner_iteration_tolerance, the use
6141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // of inner iterations in subsequent trust region minimizer
6151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // iterations is disabled.
6161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    double inner_iteration_tolerance;
6171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
6180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Minimum number of iterations for which the linear solver should
6190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // run, even if the convergence criterion is satisfied.
6201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    int min_linear_solver_iterations;
6210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
6220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Maximum number of iterations for which the linear solver should
6230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // run. If the solver does not converge in less than
6241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // max_linear_solver_iterations, then it returns MAX_ITERATIONS,
6251d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // as its termination type.
6261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    int max_linear_solver_iterations;
6270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
6280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Forcing sequence parameter. The truncated Newton solver uses
6290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // this number to control the relative accuracy with which the
6300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Newton step is computed.
6310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
6320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // This constant is passed to ConjugateGradientsSolver which uses
6330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // it to terminate the iterations when
6340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
6350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //  (Q_i - Q_{i-1})/Q_i < eta/i
6360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    double eta;
6370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
6380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Normalize the jacobian using Jacobi scaling before calling
6390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // the linear least squares solver.
6400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    bool jacobi_scaling;
6410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
6420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Logging options ---------------------------------------------------------
6430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
6440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    LoggingType logging_type;
6450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
6460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // By default the Minimizer progress is logged to VLOG(1), which
6470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // is sent to STDERR depending on the vlog level. If this flag is
6480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // set to true, and logging_type is not SILENT, the logging output
6490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // is sent to STDOUT.
6500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    bool minimizer_progress_to_stdout;
6510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
6521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // List of iterations at which the minimizer should dump the trust
6531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // region problem. Useful for testing and benchmarking. If empty
6541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // (default), no problems are dumped.
6551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    vector<int> trust_region_minimizer_iterations_to_dump;
6560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
6571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // Directory to which the problems should be written to. Should be
6581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // non-empty if trust_region_minimizer_iterations_to_dump is
6591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // non-empty and trust_region_problem_dump_format_type is not
6601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // CONSOLE.
6611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    string trust_region_problem_dump_directory;
6621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    DumpFormatType trust_region_problem_dump_format_type;
6630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
6640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Finite differences options ----------------------------------------------
6650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
6660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Check all jacobians computed by each residual block with finite
6670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // differences. This is expensive since it involves computing the
6680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // derivative by normal means (e.g. user specified, autodiff,
6690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // etc), then also computing it using finite differences. The
6700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // results are compared, and if they differ substantially, details
6710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // are printed to the log.
6720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    bool check_gradients;
6730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
6740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Relative precision to check for in the gradient checker. If the
6750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // relative difference between an element in a jacobian exceeds
6760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // this number, then the jacobian for that cost term is dumped.
6770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    double gradient_check_relative_precision;
6780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
6790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Relative shift used for taking numeric derivatives. For finite
6800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // differencing, each dimension is evaluated at slightly shifted
6810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // values; for the case of central difference, this is what gets
6820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // evaluated:
6830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
6840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //   delta = numeric_derivative_relative_step_size;
6850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //   f_initial  = f(x)
6860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //   f_forward  = f((1 + delta) * x)
6870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //   f_backward = f((1 - delta) * x)
6880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
6890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // The finite differencing is done along each dimension. The
6900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // reason to use a relative (rather than absolute) step size is
6910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // that this way, numeric differentation works for functions where
6920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // the arguments are typically large (e.g. 1e9) and when the
6930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // values are small (e.g. 1e-5). It is possible to construct
6940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // "torture cases" which break this finite difference heuristic,
6950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // but they do not come up often in practice.
6960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
6970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // TODO(keir): Pick a smarter number than the default above! In
6980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // theory a good choice is sqrt(eps) * x, which for doubles means
6990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // about 1e-8 * x. However, I have found this number too
7000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // optimistic. This number should be exposed for users to change.
7010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    double numeric_derivative_relative_step_size;
7020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
7030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // If true, the user's parameter blocks are updated at the end of
7040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // every Minimizer iteration, otherwise they are updated when the
7050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Minimizer terminates. This is useful if, for example, the user
7060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // wishes to visualize the state of the optimization every
7070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // iteration.
7080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    bool update_state_every_iteration;
7090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
7100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Callbacks that are executed at the end of each iteration of the
7110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Minimizer. An iteration may terminate midway, either due to
7120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // numerical failures or because one of the convergence tests has
7130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // been satisfied. In this case none of the callbacks are
7140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // executed.
7150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
7160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Callbacks are executed in the order that they are specified in
7170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // this vector. By default, parameter blocks are updated only at
7180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // the end of the optimization, i.e when the Minimizer
7190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // terminates. This behaviour is controlled by
7200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // update_state_every_variable. If the user wishes to have access
7210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // to the update parameter blocks when his/her callbacks are
7220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // executed, then set update_state_every_iteration to true.
7230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    //
7240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // The solver does NOT take ownership of these pointers.
7250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    vector<IterationCallback*> callbacks;
7260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong  };
7270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
72879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez  struct CERES_EXPORT Summary {
7290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    Summary();
7300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
7310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // A brief one line description of the state of the solver after
7320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // termination.
7330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    string BriefReport() const;
7340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
7350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // A full multiline description of the state of the solver after
7360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // termination.
7370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    string FullReport() const;
7380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
73979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    bool IsSolutionUsable() const;
74079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
7410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Minimizer summary -------------------------------------------------
7421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    MinimizerType minimizer_type;
7431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
74479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    TerminationType termination_type;
7450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
74679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Reason why the solver terminated.
74779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    string message;
7480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
74979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Cost of the problem (value of the objective function) before
75079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // the optimization.
7510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    double initial_cost;
75279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
75379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Cost of the problem (value of the objective function) after the
75479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // optimization.
7550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    double final_cost;
7560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
7570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // The part of the total cost that comes from residual blocks that
7580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // were held fixed by the preprocessor because all the parameter
7590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // blocks that they depend on were fixed.
7600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    double fixed_cost;
7610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
76279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // IterationSummary for each minimizer iteration in order.
7630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    vector<IterationSummary> iterations;
7640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
76579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Number of minimizer iterations in which the step was
76679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // accepted. Unless use_non_monotonic_steps is true this is also
76779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // the number of steps in which the objective function value/cost
76879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // went down.
7690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    int num_successful_steps;
77079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
77179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Number of minimizer iterations in which the step was rejected
77279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // either because it did not reduce the cost enough or the step
77379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // was not numerically valid.
7740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    int num_unsuccessful_steps;
77579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
77679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Number of times inner iterations were performed.
7771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    int num_inner_iteration_steps;
7781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
7791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    // All times reported below are wall times.
7800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
7810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // When the user calls Solve, before the actual optimization
7820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // occurs, Ceres performs a number of preprocessing steps. These
7830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // include error checks, memory allocations, and reorderings. This
7840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // time is accounted for as preprocessing time.
7850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    double preprocessor_time_in_seconds;
7860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
7870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Time spent in the TrustRegionMinimizer.
7880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    double minimizer_time_in_seconds;
7890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
7900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // After the Minimizer is finished, some time is spent in
7910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // re-evaluating residuals etc. This time is accounted for in the
7920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // postprocessor time.
7930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    double postprocessor_time_in_seconds;
7940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
7950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    // Some total of all time spent inside Ceres when Solve is called.
7960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    double total_time_in_seconds;
7970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
79879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Time (in seconds) spent in the linear solver computing the
79979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // trust region step.
8001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    double linear_solver_time_in_seconds;
80179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
80279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Time (in seconds) spent evaluating the residual vector.
8031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    double residual_evaluation_time_in_seconds;
80479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
80579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Time (in seconds) spent evaluating the jacobian matrix.
8061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    double jacobian_evaluation_time_in_seconds;
80779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
80879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Time (in seconds) spent doing inner iterations.
8091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    double inner_iteration_time_in_seconds;
8101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
81179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Number of parameter blocks in the problem.
8120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    int num_parameter_blocks;
81379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
81479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Number of parameters in the probem.
8150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    int num_parameters;
81679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
81779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Dimension of the tangent space of the problem (or the number of
81879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // columns in the Jacobian for the problem). This is different
81979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // from num_parameters if a parameter block is associated with a
82079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // LocalParameterization
8211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    int num_effective_parameters;
82279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
82379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Number of residual blocks in the problem.
8240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    int num_residual_blocks;
82579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
82679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Number of residuals in the problem.
8270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    int num_residuals;
8280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
82979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Number of parameter blocks in the problem after the inactive
83079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // and constant parameter blocks have been removed. A parameter
83179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // block is inactive if no residual block refers to it.
8320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    int num_parameter_blocks_reduced;
83379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
83479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Number of parameters in the reduced problem.
8350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    int num_parameters_reduced;
83679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
83779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Dimension of the tangent space of the reduced problem (or the
83879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // number of columns in the Jacobian for the reduced
83979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // problem). This is different from num_parameters_reduced if a
84079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // parameter block in the reduced problem is associated with a
84179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // LocalParameterization.
8421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    int num_effective_parameters_reduced;
84379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
84479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Number of residual blocks in the reduced problem.
8450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    int num_residual_blocks_reduced;
8460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
84779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    //  Number of residuals in the reduced problem.
84879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    int num_residuals_reduced;
8490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
85079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    //  Number of threads specified by the user for Jacobian and
85179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    //  residual evaluation.
8520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    int num_threads_given;
85379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
85479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Number of threads actually used by the solver for Jacobian and
85579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // residual evaluation. This number is not equal to
85679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // num_threads_given if OpenMP is not available.
8570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    int num_threads_used;
8580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
85979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    //  Number of threads specified by the user for solving the trust
86079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // region problem.
8610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    int num_linear_solver_threads_given;
86279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
86379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Number of threads actually used by the solver for solving the
86479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // trust region problem. This number is not equal to
86579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // num_threads_given if OpenMP is not available.
8660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    int num_linear_solver_threads_used;
8670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
86879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Type of the linear solver requested by the user.
8690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    LinearSolverType linear_solver_type_given;
87079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
87179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Type of the linear solver actually used. This may be different
87279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // from linear_solver_type_given if Ceres determines that the
87379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // problem structure is not compatible with the linear solver
87479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // requested or if the linear solver requested by the user is not
87579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // available, e.g. The user requested SPARSE_NORMAL_CHOLESKY but
87679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // no sparse linear algebra library was available.
8770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    LinearSolverType linear_solver_type_used;
8780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
87979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Size of the elimination groups given by the user as hints to
88079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // the linear solver.
8811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    vector<int> linear_solver_ordering_given;
88279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
88379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Size of the parameter groups used by the solver when ordering
88479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // the columns of the Jacobian.  This maybe different from
88579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // linear_solver_ordering_given if the user left
88679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // linear_solver_ordering_given blank and asked for an automatic
88779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // ordering, or if the problem contains some constant or inactive
88879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // parameter blocks.
8891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    vector<int> linear_solver_ordering_used;
8901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
89179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // True if the user asked for inner iterations to be used as part
89279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // of the optimization.
8931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    bool inner_iterations_given;
89479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
89579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // True if the user asked for inner iterations to be used as part
89679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // of the optimization and the problem structure was such that
89779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // they were actually performed. e.g., in a problem with just one
89879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // parameter block, inner iterations are not performed.
8991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    bool inner_iterations_used;
9001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
90179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Size of the parameter groups given by the user for performing
90279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // inner iterations.
9031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    vector<int> inner_iteration_ordering_given;
90479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
90579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Size of the parameter groups given used by the solver for
90679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // performing inner iterations. This maybe different from
90779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // inner_iteration_ordering_given if the user left
90879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // inner_iteration_ordering_given blank and asked for an automatic
90979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // ordering, or if the problem contains some constant or inactive
91079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // parameter blocks.
9111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    vector<int> inner_iteration_ordering_used;
9121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
91379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    //  Type of preconditioner used for solving the trust region
91479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    //  step. Only meaningful when an iterative linear solver is used.
9150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    PreconditionerType preconditioner_type;
9160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
91779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Type of clustering algorithm used for visibility based
91879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // preconditioning. Only meaningful when the preconditioner_type
91979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // is CLUSTER_JACOBI or CLUSTER_TRIDIAGONAL.
92079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    VisibilityClusteringType visibility_clustering_type;
92179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
92279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    //  Type of trust region strategy.
9230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    TrustRegionStrategyType trust_region_strategy_type;
92479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
92579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    //  Type of dogleg strategy used for solving the trust region
92679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    //  problem.
9270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong    DoglegType dogleg_type;
9281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
92979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    //  Type of the dense linear algebra library used.
930399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger    DenseLinearAlgebraLibraryType dense_linear_algebra_library_type;
93179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
93279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Type of the sparse linear algebra library used.
933399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger    SparseLinearAlgebraLibraryType sparse_linear_algebra_library_type;
9341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
93579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Type of line search direction used.
9361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    LineSearchDirectionType line_search_direction_type;
93779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
93879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // Type of the line search algorithm used.
9391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    LineSearchType line_search_type;
94079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
94179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    //  When performing line search, the degree of the polynomial used
94279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    //  to approximate the objective function.
9431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    LineSearchInterpolationType line_search_interpolation_type;
94479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez
94579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // If the line search direction is NONLINEAR_CONJUGATE_GRADIENT,
94679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // then this indicates the particular variant of non-linear
94779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // conjugate gradient used.
9481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    NonlinearConjugateGradientType nonlinear_conjugate_gradient_type;
9491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling
95079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // If the type of the line search direction is LBFGS, then this
95179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez    // indicates the rank of the Hessian approximation.
9521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling    int max_lbfgs_rank;
9530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong  };
9540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong
9550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong  // Once a least squares problem has been built, this function takes
9560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong  // the problem and optimizes it based on the values of the options
9570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong  // parameters. Upon return, a detailed summary of the work performed
9580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong  // by the preprocessor, the non-linear minmizer and the linear
9590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong  // solver are reported in the summary object.
960