solver.h revision 399f7d09e0c45af54b77b4ab9508d6f23759b927
10ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Ceres Solver - A fast non-linear least squares minimizer 20ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Copyright 2010, 2011, 2012 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" 430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongnamespace ceres { 450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongclass Problem; 470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Interface for non-linear least squares solvers. 490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongclass Solver { 500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong public: 510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual ~Solver(); 520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The options structure contains, not surprisingly, options that control how 540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the solver operates. The defaults should be suitable for a wide range of 550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // problems; however, better performance is often obtainable with tweaking. 560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The constants are defined inside types.h 580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong struct Options { 590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Default constructor that sets up a generic sparse problem. 600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Options() { 611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling minimizer_type = TRUST_REGION; 621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_direction_type = LBFGS; 631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_type = WOLFE; 641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling nonlinear_conjugate_gradient_type = FLETCHER_REEVES; 651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling max_lbfgs_rank = 20; 661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling use_approximate_eigenvalue_bfgs_scaling = false; 671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_interpolation_type = CUBIC; 681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling min_line_search_step_size = 1e-9; 691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_sufficient_function_decrease = 1e-4; 701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling max_line_search_step_contraction = 1e-3; 711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling min_line_search_step_contraction = 0.6; 721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling max_num_line_search_step_size_iterations = 20; 731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling max_num_line_search_direction_restarts = 5; 741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_sufficient_curvature_decrease = 0.9; 751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling max_line_search_step_expansion = 10.0; 760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong trust_region_strategy_type = LEVENBERG_MARQUARDT; 770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong dogleg_type = TRADITIONAL_DOGLEG; 780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong use_nonmonotonic_steps = false; 790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong max_consecutive_nonmonotonic_steps = 5; 800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong max_num_iterations = 50; 810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong max_solver_time_in_seconds = 1e9; 820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong num_threads = 1; 830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong initial_trust_region_radius = 1e4; 840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong max_trust_region_radius = 1e16; 850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong min_trust_region_radius = 1e-32; 860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong min_relative_decrease = 1e-3; 871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling min_lm_diagonal = 1e-6; 881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling max_lm_diagonal = 1e32; 890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong max_num_consecutive_invalid_steps = 5; 900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong function_tolerance = 1e-6; 910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong gradient_tolerance = 1e-10; 920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong parameter_tolerance = 1e-8; 930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#if defined(CERES_NO_SUITESPARSE) && defined(CERES_NO_CXSPARSE) 950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong linear_solver_type = DENSE_QR; 960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#else 970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong linear_solver_type = SPARSE_NORMAL_CHOLESKY; 980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#endif 990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong preconditioner_type = JACOBI; 1010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 102399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger dense_linear_algebra_library_type = EIGEN; 103399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger sparse_linear_algebra_library_type = SUITE_SPARSE; 1040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#if defined(CERES_NO_SUITESPARSE) && !defined(CERES_NO_CXSPARSE) 105399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger sparse_linear_algebra_library_type = CX_SPARSE; 1060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#endif 1070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 108399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger 1090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong num_linear_solver_threads = 1; 1100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong linear_solver_ordering = NULL; 1111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling use_postordering = false; 1121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling min_linear_solver_iterations = 1; 1131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling max_linear_solver_iterations = 500; 1140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong eta = 1e-1; 1150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong jacobi_scaling = true; 1161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling use_inner_iterations = false; 1171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling inner_iteration_tolerance = 1e-3; 1181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling inner_iteration_ordering = NULL; 1190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong logging_type = PER_MINIMIZER_ITERATION; 1200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong minimizer_progress_to_stdout = false; 1211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling trust_region_problem_dump_directory = "/tmp"; 1221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling trust_region_problem_dump_format_type = TEXTFILE; 1230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong check_gradients = false; 1240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong gradient_check_relative_precision = 1e-8; 1250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong numeric_derivative_relative_step_size = 1e-6; 1260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong update_state_every_iteration = false; 1270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ~Options(); 1300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Minimizer options ---------------------------------------- 1310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Ceres supports the two major families of optimization strategies - 1331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Trust Region and Line Search. 1341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1. The line search approach first finds a descent direction 1361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // along which the objective function will be reduced and then 1371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // computes a step size that decides how far should move along 1381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // that direction. The descent direction can be computed by 1391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // various methods, such as gradient descent, Newton's method and 1401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Quasi-Newton method. The step size can be determined either 1411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // exactly or inexactly. 1421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2. The trust region approach approximates the objective 1441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // function using using a model function (often a quadratic) over 1451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // a subset of the search space known as the trust region. If the 1461d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // model function succeeds in minimizing the true objective 1471d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // function the trust region is expanded; conversely, otherwise it 1481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // is contracted and the model optimization problem is solved 1491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // again. 1501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Trust region methods are in some sense dual to line search methods: 1521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // trust region methods first choose a step size (the size of the 1531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // trust region) and then a step direction while line search methods 1541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // first choose a step direction and then a step size. 1551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling MinimizerType minimizer_type; 1561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchDirectionType line_search_direction_type; 1581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchType line_search_type; 1591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling NonlinearConjugateGradientType nonlinear_conjugate_gradient_type; 1601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // The LBFGS hessian approximation is a low rank approximation to 1621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // the inverse of the Hessian matrix. The rank of the 1631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // approximation determines (linearly) the space and time 1641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // complexity of using the approximation. Higher the rank, the 1651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // better is the quality of the approximation. The increase in 1661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // quality is however is bounded for a number of reasons. 1671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1. The method only uses secant information and not actual 1691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // derivatives. 1701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2. The Hessian approximation is constrained to be positive 1721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // definite. 1731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // So increasing this rank to a large number will cost time and 1751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // space complexity without the corresponding increase in solution 1761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // quality. There are no hard and fast rules for choosing the 1771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // maximum rank. The best choice usually requires some problem 1781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // specific experimentation. 1791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // For more theoretical and implementation details of the LBFGS 1811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // method, please see: 1821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Nocedal, J. (1980). "Updating Quasi-Newton Matrices with 1841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Limited Storage". Mathematics of Computation 35 (151): 773–782. 1851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int max_lbfgs_rank; 1861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // As part of the (L)BFGS update step (BFGS) / right-multiply step (L-BFGS), 1881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // the initial inverse Hessian approximation is taken to be the Identity. 1891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // However, Oren showed that using instead I * \gamma, where \gamma is 1901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // chosen to approximate an eigenvalue of the true inverse Hessian can 1911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // result in improved convergence in a wide variety of cases. Setting 1921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // use_approximate_eigenvalue_bfgs_scaling to true enables this scaling. 1931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // It is important to note that approximate eigenvalue scaling does not 1951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // always improve convergence, and that it can in fact significantly degrade 1961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // performance for certain classes of problem, which is why it is disabled 1971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // by default. In particular it can degrade performance when the 1981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // sensitivity of the problem to different parameters varies significantly, 1991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // as in this case a single scalar factor fails to capture this variation 2001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // and detrimentally downscales parts of the jacobian approximation which 2011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // correspond to low-sensitivity parameters. It can also reduce the 2021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // robustness of the solution to errors in the jacobians. 2031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Oren S.S., Self-scaling variable metric (SSVM) algorithms 2051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Part II: Implementation and experiments, Management Science, 2061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 20(5), 863-874, 1974. 2071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bool use_approximate_eigenvalue_bfgs_scaling; 2081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Degree of the polynomial used to approximate the objective 2101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // function. Valid values are BISECTION, QUADRATIC and CUBIC. 2111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // BISECTION corresponds to pure backtracking search with no 2131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // interpolation. 2141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchInterpolationType line_search_interpolation_type; 2151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // If during the line search, the step_size falls below this 2171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // value, it is truncated to zero. 2181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double min_line_search_step_size; 2191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Line search parameters. 2211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Solving the line search problem exactly is computationally 2231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // prohibitive. Fortunately, line search based optimization 2241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // algorithms can still guarantee convergence if instead of an 2251d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // exact solution, the line search algorithm returns a solution 2261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // which decreases the value of the objective function 2271d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // sufficiently. More precisely, we are looking for a step_size 2281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // s.t. 2291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // f(step_size) <= f(0) + sufficient_decrease * f'(0) * step_size 2311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double line_search_sufficient_function_decrease; 2331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // In each iteration of the line search, 2351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // new_step_size >= max_line_search_step_contraction * step_size 2371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Note that by definition, for contraction: 2391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 0 < max_step_contraction < min_step_contraction < 1 2411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double max_line_search_step_contraction; 2431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // In each iteration of the line search, 2451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2461d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // new_step_size <= min_line_search_step_contraction * step_size 2471d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Note that by definition, for contraction: 2491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 0 < max_step_contraction < min_step_contraction < 1 2511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double min_line_search_step_contraction; 2531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Maximum number of trial step size iterations during each line search, 2551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // if a step size satisfying the search conditions cannot be found within 2561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // this number of trials, the line search will terminate. 2571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int max_num_line_search_step_size_iterations; 2581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Maximum number of restarts of the line search direction algorithm before 2601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // terminating the optimization. Restarts of the line search direction 2611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // algorithm occur when the current algorithm fails to produce a new descent 2621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // direction. This typically indicates a numerical failure, or a breakdown 2631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // in the validity of the approximations used. 2641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int max_num_line_search_direction_restarts; 2651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // The strong Wolfe conditions consist of the Armijo sufficient 2671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // decrease condition, and an additional requirement that the 2681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // step-size be chosen s.t. the _magnitude_ ('strong' Wolfe 2691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // conditions) of the gradient along the search direction 2701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // decreases sufficiently. Precisely, this second condition 2711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // is that we seek a step_size s.t. 2721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // |f'(step_size)| <= sufficient_curvature_decrease * |f'(0)| 2741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Where f() is the line search objective and f'() is the derivative 2761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // of f w.r.t step_size (d f / d step_size). 2771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double line_search_sufficient_curvature_decrease; 2781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // During the bracketing phase of the Wolfe search, the step size is 2801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // increased until either a point satisfying the Wolfe conditions is 2811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // found, or an upper bound for a bracket containing a point satisfying 2821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // the conditions is found. Precisely, at each iteration of the 2831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // expansion: 2841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // new_step_size <= max_step_expansion * step_size. 2861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // By definition for expansion, max_step_expansion > 1.0. 2881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double max_line_search_step_expansion; 2891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong TrustRegionStrategyType trust_region_strategy_type; 2910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Type of dogleg strategy to use. 2930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong DoglegType dogleg_type; 2940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The classical trust region methods are descent methods, in that 2960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // they only accept a point if it strictly reduces the value of 2970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the objective function. 2980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 2990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Relaxing this requirement allows the algorithm to be more 3000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // efficient in the long term at the cost of some local increase 3010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // in the value of the objective function. 3020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // This is because allowing for non-decreasing objective function 3040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // values in a princpled manner allows the algorithm to "jump over 3050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // boulders" as the method is not restricted to move into narrow 3060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // valleys while preserving its convergence properties. 3070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Setting use_nonmonotonic_steps to true enables the 3090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // non-monotonic trust region algorithm as described by Conn, 3100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Gould & Toint in "Trust Region Methods", Section 10.1. 3110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The parameter max_consecutive_nonmonotonic_steps controls the 3130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // window size used by the step selection algorithm to accept 3140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // non-monotonic steps. 3150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Even though the value of the objective function may be larger 3170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // than the minimum value encountered over the course of the 3180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // optimization, the final parameters returned to the user are the 3190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // ones corresponding to the minimum cost over all iterations. 3200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong bool use_nonmonotonic_steps; 3210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int max_consecutive_nonmonotonic_steps; 3220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Maximum number of iterations for the minimizer to run for. 3240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int max_num_iterations; 3250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Maximum time for which the minimizer should run for. 3270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double max_solver_time_in_seconds; 3280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Number of threads used by Ceres for evaluating the cost and 3300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // jacobians. 3310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_threads; 3320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Trust region minimizer settings. 3340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double initial_trust_region_radius; 3350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double max_trust_region_radius; 3360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Minimizer terminates when the trust region radius becomes 3380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // smaller than this value. 3390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double min_trust_region_radius; 3400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Lower bound for the relative decrease before a step is 3420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // accepted. 3430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double min_relative_decrease; 3440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // For the Levenberg-Marquadt algorithm, the scaled diagonal of 3460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the normal equations J'J is used to control the size of the 3470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // trust region. Extremely small and large values along the 3480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // diagonal can make this regularization scheme 3491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // fail. max_lm_diagonal and min_lm_diagonal, clamp the values of 3500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // diag(J'J) from above and below. In the normal course of 3510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // operation, the user should not have to modify these parameters. 3521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double min_lm_diagonal; 3531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double max_lm_diagonal; 3540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Sometimes due to numerical conditioning problems or linear 3560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // solver flakiness, the trust region strategy may return a 3570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // numerically invalid step that can be fixed by reducing the 3580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // trust region size. So the TrustRegionMinimizer allows for a few 3590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // successive invalid steps before it declares NUMERICAL_FAILURE. 3600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int max_num_consecutive_invalid_steps; 3610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Minimizer terminates when 3630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // (new_cost - old_cost) < function_tolerance * old_cost; 3650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double function_tolerance; 3670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Minimizer terminates when 3690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // max_i |gradient_i| < gradient_tolerance * max_i|initial_gradient_i| 3710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // This value should typically be 1e-4 * function_tolerance. 3730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double gradient_tolerance; 3740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Minimizer terminates when 3760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // |step|_2 <= parameter_tolerance * ( |x|_2 + parameter_tolerance) 3780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double parameter_tolerance; 3800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Linear least squares solver options ------------------------------------- 3820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong LinearSolverType linear_solver_type; 3840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Type of preconditioner to use with the iterative linear solvers. 3860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong PreconditionerType preconditioner_type; 3870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 388399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger // Ceres supports using multiple dense linear algebra libraries 389399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger // for dense matrix factorizations. Currently EIGEN and LAPACK are 390399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger // the valid choices. EIGEN is always available, LAPACK refers to 391399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger // the system BLAS + LAPACK library which may or may not be 392399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger // available. 393399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger // 394399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger // This setting affects the DENSE_QR, DENSE_NORMAL_CHOLESKY and 395399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger // DENSE_SCHUR solvers. For small to moderate sized probem EIGEN 396399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger // is a fine choice but for large problems, an optimized LAPACK + 397399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger // BLAS implementation can make a substantial difference in 398399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger // performance. 399399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger DenseLinearAlgebraLibraryType dense_linear_algebra_library_type; 400399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger 4010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Ceres supports using multiple sparse linear algebra libraries 4020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // for sparse matrix ordering and factorizations. Currently, 4030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // SUITE_SPARSE and CX_SPARSE are the valid choices, depending on 4040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // whether they are linked into Ceres at build time. 405399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger SparseLinearAlgebraLibraryType sparse_linear_algebra_library_type; 4060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 4070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Number of threads used by Ceres to solve the Newton 4080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // step. Currently only the SPARSE_SCHUR solver is capable of 4090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // using this setting. 4100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_linear_solver_threads; 4110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 4120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The order in which variables are eliminated in a linear solver 4130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // can have a significant of impact on the efficiency and accuracy 4140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // of the method. e.g., when doing sparse Cholesky factorization, 4150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // there are matrices for which a good ordering will give a 4160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Cholesky factor with O(n) storage, where as a bad ordering will 4170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // result in an completely dense factor. 4180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Ceres allows the user to provide varying amounts of hints to 4200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the solver about the variable elimination ordering to use. This 4210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // can range from no hints, where the solver is free to decide the 4220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // best possible ordering based on the user's choices like the 4230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // linear solver being used, to an exact order in which the 4240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // variables should be eliminated, and a variety of possibilities 4250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // in between. 4260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Instances of the ParameterBlockOrdering class are used to 4280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // communicate this information to Ceres. 4290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Formally an ordering is an ordered partitioning of the 4310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // parameter blocks, i.e, each parameter block belongs to exactly 4320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // one group, and each group has a unique non-negative integer 4330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // associated with it, that determines its order in the set of 4340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // groups. 4350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Given such an ordering, Ceres ensures that the parameter blocks in 4370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the lowest numbered group are eliminated first, and then the 4380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // parmeter blocks in the next lowest numbered group and so on. Within 4390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // each group, Ceres is free to order the parameter blocks as it 4400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // chooses. 4410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // If NULL, then all parameter blocks are assumed to be in the 4430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // same group and the solver is free to decide the best 4440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // ordering. 4450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // e.g. Consider the linear system 4470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // x + y = 3 4490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 2x + 3y = 7 4500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // There are two ways in which it can be solved. First eliminating x 4520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // from the two equations, solving for y and then back substituting 4530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // for x, or first eliminating y, solving for x and back substituting 4540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // for y. The user can construct three orderings here. 4550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // {0: x}, {1: y} - eliminate x first. 4570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // {0: y}, {1: x} - eliminate y first. 4580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // {0: x, y} - Solver gets to decide the elimination order. 4590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Thus, to have Ceres determine the ordering automatically using 4610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // heuristics, put all the variables in group 0 and to control the 4620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // ordering for every variable, create groups 0..N-1, one per 4630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // variable, in the desired order. 4640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Bundle Adjustment 4660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // ----------------- 4670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // A particular case of interest is bundle adjustment, where the user 4690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // has two options. The default is to not specify an ordering at all, 4700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the solver will see that the user wants to use a Schur type solver 4710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // and figure out the right elimination ordering. 4720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // But if the user already knows what parameter blocks are points and 4740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // what are cameras, they can save preprocessing time by partitioning 4750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the parameter blocks into two groups, one for the points and one 4760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // for the cameras, where the group containing the points has an id 4770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // smaller than the group containing cameras. 4780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Once assigned, Solver::Options owns this pointer and will 4800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // deallocate the memory when destroyed. 4810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ParameterBlockOrdering* linear_solver_ordering; 4820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 4831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Sparse Cholesky factorization algorithms use a fill-reducing 4841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // ordering to permute the columns of the Jacobian matrix. There 4851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // are two ways of doing this. 4861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1. Compute the Jacobian matrix in some order and then have the 4881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // factorization algorithm permute the columns of the Jacobian. 4891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2. Compute the Jacobian with its columns already permuted. 4911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // The first option incurs a significant memory penalty. The 4931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // factorization algorithm has to make a copy of the permuted 4941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Jacobian matrix, thus Ceres pre-permutes the columns of the 4951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Jacobian matrix and generally speaking, there is no performance 4961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // penalty for doing so. 4971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // In some rare cases, it is worth using a more complicated 4991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // reordering algorithm which has slightly better runtime 5001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // performance at the expense of an extra copy of the Jacobian 5011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // matrix. Setting use_postordering to true enables this tradeoff. 5021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bool use_postordering; 5030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 5040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Some non-linear least squares problems have additional 5050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // structure in the way the parameter blocks interact that it is 5060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // beneficial to modify the way the trust region step is computed. 5070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // e.g., consider the following regression problem 5090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // y = a_1 exp(b_1 x) + a_2 exp(b_3 x^2 + c_1) 5110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Given a set of pairs{(x_i, y_i)}, the user wishes to estimate 5130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // a_1, a_2, b_1, b_2, and c_1. 5140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Notice here that the expression on the left is linear in a_1 5160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // and a_2, and given any value for b_1, b_2 and c_1, it is 5170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // possible to use linear regression to estimate the optimal 5180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // values of a_1 and a_2. Indeed, its possible to analytically 5190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // eliminate the variables a_1 and a_2 from the problem all 5200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // together. Problems like these are known as separable least 5210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // squares problem and the most famous algorithm for solving them 5220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // is the Variable Projection algorithm invented by Golub & 5230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Pereyra. 5240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Similar structure can be found in the matrix factorization with 5260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // missing data problem. There the corresponding algorithm is 5270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // known as Wiberg's algorithm. 5280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Ruhe & Wedin (Algorithms for Separable Nonlinear Least Squares 5300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Problems, SIAM Reviews, 22(3), 1980) present an analyis of 5310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // various algorithms for solving separable non-linear least 5320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // squares problems and refer to "Variable Projection" as 5330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Algorithm I in their paper. 5340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Implementing Variable Projection is tedious and expensive, and 5360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // they present a simpler algorithm, which they refer to as 5370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Algorithm II, where once the Newton/Trust Region step has been 5380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // computed for the whole problem (a_1, a_2, b_1, b_2, c_1) and 5390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // additional optimization step is performed to estimate a_1 and 5400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // a_2 exactly. 5410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // This idea can be generalized to cases where the residual is not 5430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // linear in a_1 and a_2, i.e., Solve for the trust region step 5440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // for the full problem, and then use it as the starting point to 5450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // further optimize just a_1 and a_2. For the linear case, this 5460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // amounts to doing a single linear least squares solve. For 5470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // non-linear problems, any method for solving the a_1 and a_2 5480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // optimization problems will do. The only constraint on a_1 and 5490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // a_2 is that they do not co-occur in any residual block. 5500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // This idea can be further generalized, by not just optimizing 5520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // (a_1, a_2), but decomposing the graph corresponding to the 5530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Hessian matrix's sparsity structure in a collection of 5540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // non-overlapping independent sets and optimizing each of them. 5550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Setting "use_inner_iterations" to true enables the use of this 5570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // non-linear generalization of Ruhe & Wedin's Algorithm II. This 5580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // version of Ceres has a higher iteration complexity, but also 5590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // displays better convergence behaviour per iteration. Setting 5600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Solver::Options::num_threads to the maximum number possible is 5610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // highly recommended. 5620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong bool use_inner_iterations; 5630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 5640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // If inner_iterations is true, then the user has two choices. 5650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 1. Let the solver heuristically decide which parameter blocks 5670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // to optimize in each inner iteration. To do this leave 5680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Solver::Options::inner_iteration_ordering untouched. 5690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 2. Specify a collection of of ordered independent sets. Where 5710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the lower numbered groups are optimized before the higher 5721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // number groups. Each group must be an independent set. Not 5731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // all parameter blocks need to be present in the ordering. 5740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ParameterBlockOrdering* inner_iteration_ordering; 5750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 5761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Generally speaking, inner iterations make significant progress 5771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // in the early stages of the solve and then their contribution 5781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // drops down sharply, at which point the time spent doing inner 5791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // iterations is not worth it. 5801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 5811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Once the relative decrease in the objective function due to 5821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // inner iterations drops below inner_iteration_tolerance, the use 5831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // of inner iterations in subsequent trust region minimizer 5841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // iterations is disabled. 5851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double inner_iteration_tolerance; 5861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Minimum number of iterations for which the linear solver should 5880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // run, even if the convergence criterion is satisfied. 5891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int min_linear_solver_iterations; 5900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 5910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Maximum number of iterations for which the linear solver should 5920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // run. If the solver does not converge in less than 5931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // max_linear_solver_iterations, then it returns MAX_ITERATIONS, 5941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // as its termination type. 5951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int max_linear_solver_iterations; 5960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 5970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Forcing sequence parameter. The truncated Newton solver uses 5980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // this number to control the relative accuracy with which the 5990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Newton step is computed. 6000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 6010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // This constant is passed to ConjugateGradientsSolver which uses 6020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // it to terminate the iterations when 6030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 6040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // (Q_i - Q_{i-1})/Q_i < eta/i 6050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double eta; 6060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Normalize the jacobian using Jacobi scaling before calling 6080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the linear least squares solver. 6090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong bool jacobi_scaling; 6100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Logging options --------------------------------------------------------- 6120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong LoggingType logging_type; 6140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // By default the Minimizer progress is logged to VLOG(1), which 6160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // is sent to STDERR depending on the vlog level. If this flag is 6170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // set to true, and logging_type is not SILENT, the logging output 6180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // is sent to STDOUT. 6190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong bool minimizer_progress_to_stdout; 6200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // List of iterations at which the minimizer should dump the trust 6221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // region problem. Useful for testing and benchmarking. If empty 6231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // (default), no problems are dumped. 6241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling vector<int> trust_region_minimizer_iterations_to_dump; 6250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Directory to which the problems should be written to. Should be 6271d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // non-empty if trust_region_minimizer_iterations_to_dump is 6281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // non-empty and trust_region_problem_dump_format_type is not 6291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // CONSOLE. 6301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling string trust_region_problem_dump_directory; 6311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling DumpFormatType trust_region_problem_dump_format_type; 6320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Finite differences options ---------------------------------------------- 6340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Check all jacobians computed by each residual block with finite 6360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // differences. This is expensive since it involves computing the 6370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // derivative by normal means (e.g. user specified, autodiff, 6380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // etc), then also computing it using finite differences. The 6390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // results are compared, and if they differ substantially, details 6400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // are printed to the log. 6410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong bool check_gradients; 6420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Relative precision to check for in the gradient checker. If the 6440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // relative difference between an element in a jacobian exceeds 6450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // this number, then the jacobian for that cost term is dumped. 6460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double gradient_check_relative_precision; 6470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Relative shift used for taking numeric derivatives. For finite 6490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // differencing, each dimension is evaluated at slightly shifted 6500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // values; for the case of central difference, this is what gets 6510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // evaluated: 6520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 6530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // delta = numeric_derivative_relative_step_size; 6540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // f_initial = f(x) 6550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // f_forward = f((1 + delta) * x) 6560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // f_backward = f((1 - delta) * x) 6570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 6580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The finite differencing is done along each dimension. The 6590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // reason to use a relative (rather than absolute) step size is 6600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // that this way, numeric differentation works for functions where 6610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the arguments are typically large (e.g. 1e9) and when the 6620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // values are small (e.g. 1e-5). It is possible to construct 6630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // "torture cases" which break this finite difference heuristic, 6640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // but they do not come up often in practice. 6650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 6660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // TODO(keir): Pick a smarter number than the default above! In 6670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // theory a good choice is sqrt(eps) * x, which for doubles means 6680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // about 1e-8 * x. However, I have found this number too 6690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // optimistic. This number should be exposed for users to change. 6700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double numeric_derivative_relative_step_size; 6710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // If true, the user's parameter blocks are updated at the end of 6730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // every Minimizer iteration, otherwise they are updated when the 6740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Minimizer terminates. This is useful if, for example, the user 6750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // wishes to visualize the state of the optimization every 6760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // iteration. 6770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong bool update_state_every_iteration; 6780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Callbacks that are executed at the end of each iteration of the 6800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Minimizer. An iteration may terminate midway, either due to 6810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // numerical failures or because one of the convergence tests has 6820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // been satisfied. In this case none of the callbacks are 6830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // executed. 6840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Callbacks are executed in the order that they are specified in 6860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // this vector. By default, parameter blocks are updated only at 6870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the end of the optimization, i.e when the Minimizer 6880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // terminates. This behaviour is controlled by 6890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // update_state_every_variable. If the user wishes to have access 6900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // to the update parameter blocks when his/her callbacks are 6910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // executed, then set update_state_every_iteration to true. 6920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 6930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The solver does NOT take ownership of these pointers. 6940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong vector<IterationCallback*> callbacks; 6950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // If non-empty, a summary of the execution of the solver is 6970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // recorded to this file. 6980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong string solver_log; 6990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong }; 7000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong struct Summary { 7020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Summary(); 7030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // A brief one line description of the state of the solver after 7050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // termination. 7060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong string BriefReport() const; 7070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // A full multiline description of the state of the solver after 7090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // termination. 7100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong string FullReport() const; 7110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Minimizer summary ------------------------------------------------- 7131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling MinimizerType minimizer_type; 7141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong SolverTerminationType termination_type; 7160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // If the solver did not run, or there was a failure, a 7180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // description of the error. 7190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong string error; 7200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Cost of the problem before and after the optimization. See 7220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // problem.h for definition of the cost of a problem. 7230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double initial_cost; 7240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double final_cost; 7250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The part of the total cost that comes from residual blocks that 7270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // were held fixed by the preprocessor because all the parameter 7280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // blocks that they depend on were fixed. 7290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double fixed_cost; 7300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong vector<IterationSummary> iterations; 7320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_successful_steps; 7340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_unsuccessful_steps; 7351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int num_inner_iteration_steps; 7361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // All times reported below are wall times. 7380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // When the user calls Solve, before the actual optimization 7400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // occurs, Ceres performs a number of preprocessing steps. These 7410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // include error checks, memory allocations, and reorderings. This 7420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // time is accounted for as preprocessing time. 7430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double preprocessor_time_in_seconds; 7440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Time spent in the TrustRegionMinimizer. 7460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double minimizer_time_in_seconds; 7470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // After the Minimizer is finished, some time is spent in 7490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // re-evaluating residuals etc. This time is accounted for in the 7500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // postprocessor time. 7510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double postprocessor_time_in_seconds; 7520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Some total of all time spent inside Ceres when Solve is called. 7540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double total_time_in_seconds; 7550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double linear_solver_time_in_seconds; 7571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double residual_evaluation_time_in_seconds; 7581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double jacobian_evaluation_time_in_seconds; 7591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double inner_iteration_time_in_seconds; 7601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Preprocessor summary. 7620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_parameter_blocks; 7630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_parameters; 7641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int num_effective_parameters; 7650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_residual_blocks; 7660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_residuals; 7670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_parameter_blocks_reduced; 7690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_parameters_reduced; 7701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int num_effective_parameters_reduced; 7710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_residual_blocks_reduced; 7720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_residuals_reduced; 7730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_eliminate_blocks_given; 7750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_eliminate_blocks_used; 7760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_threads_given; 7780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_threads_used; 7790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_linear_solver_threads_given; 7810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_linear_solver_threads_used; 7820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong LinearSolverType linear_solver_type_given; 7840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong LinearSolverType linear_solver_type_used; 7850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling vector<int> linear_solver_ordering_given; 7871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling vector<int> linear_solver_ordering_used; 7881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bool inner_iterations_given; 7901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bool inner_iterations_used; 7911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling vector<int> inner_iteration_ordering_given; 7931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling vector<int> inner_iteration_ordering_used; 7941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong PreconditionerType preconditioner_type; 7960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong TrustRegionStrategyType trust_region_strategy_type; 7980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong DoglegType dogleg_type; 7991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 800399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger DenseLinearAlgebraLibraryType dense_linear_algebra_library_type; 801399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger SparseLinearAlgebraLibraryType sparse_linear_algebra_library_type; 8021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 8031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchDirectionType line_search_direction_type; 8041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchType line_search_type; 8051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchInterpolationType line_search_interpolation_type; 8061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling NonlinearConjugateGradientType nonlinear_conjugate_gradient_type; 8071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 8081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int max_lbfgs_rank; 8090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong }; 8100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 8110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Once a least squares problem has been built, this function takes 8120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the problem and optimizes it based on the values of the options 8130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // parameters. Upon return, a detailed summary of the work performed 8140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // by the preprocessor, the non-linear minmizer and the linear 8150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // solver are reported in the summary object. 8160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual void Solve(const Options& options, 8170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Problem* problem, 8180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Solver::Summary* summary); 8190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong}; 8200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 8210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Helper function which avoids going through the interface. 8220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongvoid Solve(const Solver::Options& options, 8230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Problem* problem, 8240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Solver::Summary* summary); 8250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 8260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} // namespace ceres 8270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 8280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#endif // CERES_PUBLIC_SOLVER_H_ 829