solver.h revision 1d2624a10e2c559f8ba9ef89eaa30832c0a83a96
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; 761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 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 950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#if defined(CERES_NO_SUITESPARSE) && defined(CERES_NO_CXSPARSE) 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; 1020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong sparse_linear_algebra_library = SUITE_SPARSE; 1040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#if defined(CERES_NO_SUITESPARSE) && !defined(CERES_NO_CXSPARSE) 1050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong sparse_linear_algebra_library = CX_SPARSE; 1060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#endif 1070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong num_linear_solver_threads = 1; 1090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong linear_solver_ordering = NULL; 1101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling use_postordering = false; 1111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling min_linear_solver_iterations = 1; 1121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling max_linear_solver_iterations = 500; 1130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong eta = 1e-1; 1140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong jacobi_scaling = true; 1151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling use_inner_iterations = false; 1161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling inner_iteration_tolerance = 1e-3; 1171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling inner_iteration_ordering = NULL; 1180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong logging_type = PER_MINIMIZER_ITERATION; 1190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong minimizer_progress_to_stdout = false; 1201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling trust_region_problem_dump_directory = "/tmp"; 1211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling trust_region_problem_dump_format_type = TEXTFILE; 1220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong check_gradients = false; 1230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong gradient_check_relative_precision = 1e-8; 1240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong numeric_derivative_relative_step_size = 1e-6; 1250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong update_state_every_iteration = false; 1260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ~Options(); 1290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Minimizer options ---------------------------------------- 1300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Ceres supports the two major families of optimization strategies - 1321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Trust Region and Line Search. 1331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1. The line search approach first finds a descent direction 1351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // along which the objective function will be reduced and then 1361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // computes a step size that decides how far should move along 1371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // that direction. The descent direction can be computed by 1381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // various methods, such as gradient descent, Newton's method and 1391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Quasi-Newton method. The step size can be determined either 1401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // exactly or inexactly. 1411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2. The trust region approach approximates the objective 1431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // function using using a model function (often a quadratic) over 1441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // a subset of the search space known as the trust region. If the 1451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // model function succeeds in minimizing the true objective 1461d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // function the trust region is expanded; conversely, otherwise it 1471d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // is contracted and the model optimization problem is solved 1481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // again. 1491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Trust region methods are in some sense dual to line search methods: 1511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // trust region methods first choose a step size (the size of the 1521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // trust region) and then a step direction while line search methods 1531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // first choose a step direction and then a step size. 1541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling MinimizerType minimizer_type; 1551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchDirectionType line_search_direction_type; 1571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchType line_search_type; 1581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling NonlinearConjugateGradientType nonlinear_conjugate_gradient_type; 1591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // The LBFGS hessian approximation is a low rank approximation to 1611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // the inverse of the Hessian matrix. The rank of the 1621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // approximation determines (linearly) the space and time 1631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // complexity of using the approximation. Higher the rank, the 1641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // better is the quality of the approximation. The increase in 1651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // quality is however is bounded for a number of reasons. 1661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1. The method only uses secant information and not actual 1681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // derivatives. 1691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2. The Hessian approximation is constrained to be positive 1711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // definite. 1721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // So increasing this rank to a large number will cost time and 1741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // space complexity without the corresponding increase in solution 1751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // quality. There are no hard and fast rules for choosing the 1761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // maximum rank. The best choice usually requires some problem 1771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // specific experimentation. 1781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // For more theoretical and implementation details of the LBFGS 1801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // method, please see: 1811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Nocedal, J. (1980). "Updating Quasi-Newton Matrices with 1831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Limited Storage". Mathematics of Computation 35 (151): 773–782. 1841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int max_lbfgs_rank; 1851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // As part of the (L)BFGS update step (BFGS) / right-multiply step (L-BFGS), 1871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // the initial inverse Hessian approximation is taken to be the Identity. 1881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // However, Oren showed that using instead I * \gamma, where \gamma is 1891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // chosen to approximate an eigenvalue of the true inverse Hessian can 1901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // result in improved convergence in a wide variety of cases. Setting 1911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // use_approximate_eigenvalue_bfgs_scaling to true enables this scaling. 1921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // It is important to note that approximate eigenvalue scaling does not 1941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // always improve convergence, and that it can in fact significantly degrade 1951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // performance for certain classes of problem, which is why it is disabled 1961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // by default. In particular it can degrade performance when the 1971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // sensitivity of the problem to different parameters varies significantly, 1981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // as in this case a single scalar factor fails to capture this variation 1991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // and detrimentally downscales parts of the jacobian approximation which 2001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // correspond to low-sensitivity parameters. It can also reduce the 2011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // robustness of the solution to errors in the jacobians. 2021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Oren S.S., Self-scaling variable metric (SSVM) algorithms 2041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Part II: Implementation and experiments, Management Science, 2051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 20(5), 863-874, 1974. 2061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bool use_approximate_eigenvalue_bfgs_scaling; 2071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Degree of the polynomial used to approximate the objective 2091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // function. Valid values are BISECTION, QUADRATIC and CUBIC. 2101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // BISECTION corresponds to pure backtracking search with no 2121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // interpolation. 2131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchInterpolationType line_search_interpolation_type; 2141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // If during the line search, the step_size falls below this 2161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // value, it is truncated to zero. 2171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double min_line_search_step_size; 2181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Line search parameters. 2201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Solving the line search problem exactly is computationally 2221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // prohibitive. Fortunately, line search based optimization 2231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // algorithms can still guarantee convergence if instead of an 2241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // exact solution, the line search algorithm returns a solution 2251d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // which decreases the value of the objective function 2261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // sufficiently. More precisely, we are looking for a step_size 2271d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // s.t. 2281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // f(step_size) <= f(0) + sufficient_decrease * f'(0) * step_size 2301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double line_search_sufficient_function_decrease; 2321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // In each iteration of the line search, 2341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // new_step_size >= max_line_search_step_contraction * step_size 2361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Note that by definition, for contraction: 2381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 0 < max_step_contraction < min_step_contraction < 1 2401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double max_line_search_step_contraction; 2421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // In each iteration of the line search, 2441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // new_step_size <= min_line_search_step_contraction * step_size 2461d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2471d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Note that by definition, for contraction: 2481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 0 < max_step_contraction < min_step_contraction < 1 2501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double min_line_search_step_contraction; 2521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Maximum number of trial step size iterations during each line search, 2541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // if a step size satisfying the search conditions cannot be found within 2551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // this number of trials, the line search will terminate. 2561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int max_num_line_search_step_size_iterations; 2571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Maximum number of restarts of the line search direction algorithm before 2591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // terminating the optimization. Restarts of the line search direction 2601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // algorithm occur when the current algorithm fails to produce a new descent 2611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // direction. This typically indicates a numerical failure, or a breakdown 2621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // in the validity of the approximations used. 2631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int max_num_line_search_direction_restarts; 2641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // The strong Wolfe conditions consist of the Armijo sufficient 2661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // decrease condition, and an additional requirement that the 2671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // step-size be chosen s.t. the _magnitude_ ('strong' Wolfe 2681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // conditions) of the gradient along the search direction 2691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // decreases sufficiently. Precisely, this second condition 2701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // is that we seek a step_size s.t. 2711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // |f'(step_size)| <= sufficient_curvature_decrease * |f'(0)| 2731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Where f() is the line search objective and f'() is the derivative 2751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // of f w.r.t step_size (d f / d step_size). 2761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double line_search_sufficient_curvature_decrease; 2771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // During the bracketing phase of the Wolfe search, the step size is 2791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // increased until either a point satisfying the Wolfe conditions is 2801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // found, or an upper bound for a bracket containing a point satisfying 2811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // the conditions is found. Precisely, at each iteration of the 2821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // expansion: 2831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // new_step_size <= max_step_expansion * step_size. 2851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // By definition for expansion, max_step_expansion > 1.0. 2871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double max_line_search_step_expansion; 2881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong TrustRegionStrategyType trust_region_strategy_type; 2900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Type of dogleg strategy to use. 2920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong DoglegType dogleg_type; 2930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The classical trust region methods are descent methods, in that 2950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // they only accept a point if it strictly reduces the value of 2960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the objective function. 2970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 2980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Relaxing this requirement allows the algorithm to be more 2990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // efficient in the long term at the cost of some local increase 3000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // in the value of the objective function. 3010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // This is because allowing for non-decreasing objective function 3030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // values in a princpled manner allows the algorithm to "jump over 3040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // boulders" as the method is not restricted to move into narrow 3050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // valleys while preserving its convergence properties. 3060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Setting use_nonmonotonic_steps to true enables the 3080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // non-monotonic trust region algorithm as described by Conn, 3090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Gould & Toint in "Trust Region Methods", Section 10.1. 3100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The parameter max_consecutive_nonmonotonic_steps controls the 3120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // window size used by the step selection algorithm to accept 3130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // non-monotonic steps. 3140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Even though the value of the objective function may be larger 3160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // than the minimum value encountered over the course of the 3170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // optimization, the final parameters returned to the user are the 3180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // ones corresponding to the minimum cost over all iterations. 3190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong bool use_nonmonotonic_steps; 3200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int max_consecutive_nonmonotonic_steps; 3210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Maximum number of iterations for the minimizer to run for. 3230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int max_num_iterations; 3240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Maximum time for which the minimizer should run for. 3260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double max_solver_time_in_seconds; 3270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Number of threads used by Ceres for evaluating the cost and 3290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // jacobians. 3300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_threads; 3310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Trust region minimizer settings. 3330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double initial_trust_region_radius; 3340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double max_trust_region_radius; 3350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Minimizer terminates when the trust region radius becomes 3370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // smaller than this value. 3380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double min_trust_region_radius; 3390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Lower bound for the relative decrease before a step is 3410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // accepted. 3420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double min_relative_decrease; 3430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // For the Levenberg-Marquadt algorithm, the scaled diagonal of 3450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the normal equations J'J is used to control the size of the 3460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // trust region. Extremely small and large values along the 3470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // diagonal can make this regularization scheme 3481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // fail. max_lm_diagonal and min_lm_diagonal, clamp the values of 3490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // diag(J'J) from above and below. In the normal course of 3500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // operation, the user should not have to modify these parameters. 3511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double min_lm_diagonal; 3521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double max_lm_diagonal; 3530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Sometimes due to numerical conditioning problems or linear 3550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // solver flakiness, the trust region strategy may return a 3560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // numerically invalid step that can be fixed by reducing the 3570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // trust region size. So the TrustRegionMinimizer allows for a few 3580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // successive invalid steps before it declares NUMERICAL_FAILURE. 3590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int max_num_consecutive_invalid_steps; 3600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Minimizer terminates when 3620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // (new_cost - old_cost) < function_tolerance * old_cost; 3640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double function_tolerance; 3660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Minimizer terminates when 3680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // max_i |gradient_i| < gradient_tolerance * max_i|initial_gradient_i| 3700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // This value should typically be 1e-4 * function_tolerance. 3720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double gradient_tolerance; 3730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Minimizer terminates when 3750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // |step|_2 <= parameter_tolerance * ( |x|_2 + parameter_tolerance) 3770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double parameter_tolerance; 3790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Linear least squares solver options ------------------------------------- 3810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong LinearSolverType linear_solver_type; 3830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Type of preconditioner to use with the iterative linear solvers. 3850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong PreconditionerType preconditioner_type; 3860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Ceres supports using multiple sparse linear algebra libraries 3880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // for sparse matrix ordering and factorizations. Currently, 3890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // SUITE_SPARSE and CX_SPARSE are the valid choices, depending on 3900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // whether they are linked into Ceres at build time. 3910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong SparseLinearAlgebraLibraryType sparse_linear_algebra_library; 3920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Number of threads used by Ceres to solve the Newton 3940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // step. Currently only the SPARSE_SCHUR solver is capable of 3950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // using this setting. 3960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_linear_solver_threads; 3970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The order in which variables are eliminated in a linear solver 3990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // can have a significant of impact on the efficiency and accuracy 4000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // of the method. e.g., when doing sparse Cholesky factorization, 4010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // there are matrices for which a good ordering will give a 4020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Cholesky factor with O(n) storage, where as a bad ordering will 4030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // result in an completely dense factor. 4040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Ceres allows the user to provide varying amounts of hints to 4060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the solver about the variable elimination ordering to use. This 4070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // can range from no hints, where the solver is free to decide the 4080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // best possible ordering based on the user's choices like the 4090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // linear solver being used, to an exact order in which the 4100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // variables should be eliminated, and a variety of possibilities 4110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // in between. 4120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Instances of the ParameterBlockOrdering class are used to 4140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // communicate this information to Ceres. 4150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Formally an ordering is an ordered partitioning of the 4170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // parameter blocks, i.e, each parameter block belongs to exactly 4180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // one group, and each group has a unique non-negative integer 4190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // associated with it, that determines its order in the set of 4200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // groups. 4210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Given such an ordering, Ceres ensures that the parameter blocks in 4230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the lowest numbered group are eliminated first, and then the 4240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // parmeter blocks in the next lowest numbered group and so on. Within 4250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // each group, Ceres is free to order the parameter blocks as it 4260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // chooses. 4270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // If NULL, then all parameter blocks are assumed to be in the 4290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // same group and the solver is free to decide the best 4300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // ordering. 4310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // e.g. Consider the linear system 4330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // x + y = 3 4350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 2x + 3y = 7 4360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // There are two ways in which it can be solved. First eliminating x 4380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // from the two equations, solving for y and then back substituting 4390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // for x, or first eliminating y, solving for x and back substituting 4400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // for y. The user can construct three orderings here. 4410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // {0: x}, {1: y} - eliminate x first. 4430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // {0: y}, {1: x} - eliminate y first. 4440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // {0: x, y} - Solver gets to decide the elimination order. 4450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Thus, to have Ceres determine the ordering automatically using 4470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // heuristics, put all the variables in group 0 and to control the 4480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // ordering for every variable, create groups 0..N-1, one per 4490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // variable, in the desired order. 4500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Bundle Adjustment 4520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // ----------------- 4530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // A particular case of interest is bundle adjustment, where the user 4550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // has two options. The default is to not specify an ordering at all, 4560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the solver will see that the user wants to use a Schur type solver 4570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // and figure out the right elimination ordering. 4580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // But if the user already knows what parameter blocks are points and 4600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // what are cameras, they can save preprocessing time by partitioning 4610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the parameter blocks into two groups, one for the points and one 4620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // for the cameras, where the group containing the points has an id 4630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // smaller than the group containing cameras. 4640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Once assigned, Solver::Options owns this pointer and will 4660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // deallocate the memory when destroyed. 4670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ParameterBlockOrdering* linear_solver_ordering; 4680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 4691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Sparse Cholesky factorization algorithms use a fill-reducing 4701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // ordering to permute the columns of the Jacobian matrix. There 4711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // are two ways of doing this. 4721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1. Compute the Jacobian matrix in some order and then have the 4741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // factorization algorithm permute the columns of the Jacobian. 4751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2. Compute the Jacobian with its columns already permuted. 4771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // The first option incurs a significant memory penalty. The 4791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // factorization algorithm has to make a copy of the permuted 4801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Jacobian matrix, thus Ceres pre-permutes the columns of the 4811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Jacobian matrix and generally speaking, there is no performance 4821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // penalty for doing so. 4831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // In some rare cases, it is worth using a more complicated 4851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // reordering algorithm which has slightly better runtime 4861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // performance at the expense of an extra copy of the Jacobian 4871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // matrix. Setting use_postordering to true enables this tradeoff. 4881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bool use_postordering; 4890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 4900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Some non-linear least squares problems have additional 4910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // structure in the way the parameter blocks interact that it is 4920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // beneficial to modify the way the trust region step is computed. 4930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // e.g., consider the following regression problem 4950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // y = a_1 exp(b_1 x) + a_2 exp(b_3 x^2 + c_1) 4970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Given a set of pairs{(x_i, y_i)}, the user wishes to estimate 4990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // a_1, a_2, b_1, b_2, and c_1. 5000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Notice here that the expression on the left is linear in a_1 5020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // and a_2, and given any value for b_1, b_2 and c_1, it is 5030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // possible to use linear regression to estimate the optimal 5040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // values of a_1 and a_2. Indeed, its possible to analytically 5050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // eliminate the variables a_1 and a_2 from the problem all 5060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // together. Problems like these are known as separable least 5070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // squares problem and the most famous algorithm for solving them 5080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // is the Variable Projection algorithm invented by Golub & 5090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Pereyra. 5100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Similar structure can be found in the matrix factorization with 5120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // missing data problem. There the corresponding algorithm is 5130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // known as Wiberg's algorithm. 5140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Ruhe & Wedin (Algorithms for Separable Nonlinear Least Squares 5160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Problems, SIAM Reviews, 22(3), 1980) present an analyis of 5170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // various algorithms for solving separable non-linear least 5180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // squares problems and refer to "Variable Projection" as 5190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Algorithm I in their paper. 5200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Implementing Variable Projection is tedious and expensive, and 5220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // they present a simpler algorithm, which they refer to as 5230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Algorithm II, where once the Newton/Trust Region step has been 5240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // computed for the whole problem (a_1, a_2, b_1, b_2, c_1) and 5250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // additional optimization step is performed to estimate a_1 and 5260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // a_2 exactly. 5270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // This idea can be generalized to cases where the residual is not 5290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // linear in a_1 and a_2, i.e., Solve for the trust region step 5300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // for the full problem, and then use it as the starting point to 5310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // further optimize just a_1 and a_2. For the linear case, this 5320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // amounts to doing a single linear least squares solve. For 5330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // non-linear problems, any method for solving the a_1 and a_2 5340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // optimization problems will do. The only constraint on a_1 and 5350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // a_2 is that they do not co-occur in any residual block. 5360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // This idea can be further generalized, by not just optimizing 5380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // (a_1, a_2), but decomposing the graph corresponding to the 5390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Hessian matrix's sparsity structure in a collection of 5400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // non-overlapping independent sets and optimizing each of them. 5410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Setting "use_inner_iterations" to true enables the use of this 5430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // non-linear generalization of Ruhe & Wedin's Algorithm II. This 5440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // version of Ceres has a higher iteration complexity, but also 5450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // displays better convergence behaviour per iteration. Setting 5460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Solver::Options::num_threads to the maximum number possible is 5470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // highly recommended. 5480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong bool use_inner_iterations; 5490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 5500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // If inner_iterations is true, then the user has two choices. 5510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 1. Let the solver heuristically decide which parameter blocks 5530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // to optimize in each inner iteration. To do this leave 5540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Solver::Options::inner_iteration_ordering untouched. 5550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 2. Specify a collection of of ordered independent sets. Where 5570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the lower numbered groups are optimized before the higher 5581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // number groups. Each group must be an independent set. Not 5591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // all parameter blocks need to be present in the ordering. 5600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ParameterBlockOrdering* inner_iteration_ordering; 5610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 5621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Generally speaking, inner iterations make significant progress 5631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // in the early stages of the solve and then their contribution 5641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // drops down sharply, at which point the time spent doing inner 5651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // iterations is not worth it. 5661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 5671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Once the relative decrease in the objective function due to 5681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // inner iterations drops below inner_iteration_tolerance, the use 5691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // of inner iterations in subsequent trust region minimizer 5701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // iterations is disabled. 5711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double inner_iteration_tolerance; 5721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Minimum number of iterations for which the linear solver should 5740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // run, even if the convergence criterion is satisfied. 5751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int min_linear_solver_iterations; 5760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 5770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Maximum number of iterations for which the linear solver should 5780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // run. If the solver does not converge in less than 5791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // max_linear_solver_iterations, then it returns MAX_ITERATIONS, 5801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // as its termination type. 5811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int max_linear_solver_iterations; 5820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 5830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Forcing sequence parameter. The truncated Newton solver uses 5840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // this number to control the relative accuracy with which the 5850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Newton step is computed. 5860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // This constant is passed to ConjugateGradientsSolver which uses 5880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // it to terminate the iterations when 5890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 5900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // (Q_i - Q_{i-1})/Q_i < eta/i 5910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double eta; 5920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 5930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Normalize the jacobian using Jacobi scaling before calling 5940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the linear least squares solver. 5950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong bool jacobi_scaling; 5960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 5970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Logging options --------------------------------------------------------- 5980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 5990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong LoggingType logging_type; 6000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // By default the Minimizer progress is logged to VLOG(1), which 6020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // is sent to STDERR depending on the vlog level. If this flag is 6030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // set to true, and logging_type is not SILENT, the logging output 6040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // is sent to STDOUT. 6050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong bool minimizer_progress_to_stdout; 6060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // List of iterations at which the minimizer should dump the trust 6081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // region problem. Useful for testing and benchmarking. If empty 6091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // (default), no problems are dumped. 6101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling vector<int> trust_region_minimizer_iterations_to_dump; 6110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Directory to which the problems should be written to. Should be 6131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // non-empty if trust_region_minimizer_iterations_to_dump is 6141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // non-empty and trust_region_problem_dump_format_type is not 6151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // CONSOLE. 6161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling string trust_region_problem_dump_directory; 6171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling DumpFormatType trust_region_problem_dump_format_type; 6180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Finite differences options ---------------------------------------------- 6200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Check all jacobians computed by each residual block with finite 6220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // differences. This is expensive since it involves computing the 6230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // derivative by normal means (e.g. user specified, autodiff, 6240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // etc), then also computing it using finite differences. The 6250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // results are compared, and if they differ substantially, details 6260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // are printed to the log. 6270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong bool check_gradients; 6280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Relative precision to check for in the gradient checker. If the 6300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // relative difference between an element in a jacobian exceeds 6310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // this number, then the jacobian for that cost term is dumped. 6320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double gradient_check_relative_precision; 6330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Relative shift used for taking numeric derivatives. For finite 6350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // differencing, each dimension is evaluated at slightly shifted 6360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // values; for the case of central difference, this is what gets 6370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // evaluated: 6380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 6390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // delta = numeric_derivative_relative_step_size; 6400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // f_initial = f(x) 6410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // f_forward = f((1 + delta) * x) 6420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // f_backward = f((1 - delta) * x) 6430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 6440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The finite differencing is done along each dimension. The 6450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // reason to use a relative (rather than absolute) step size is 6460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // that this way, numeric differentation works for functions where 6470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the arguments are typically large (e.g. 1e9) and when the 6480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // values are small (e.g. 1e-5). It is possible to construct 6490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // "torture cases" which break this finite difference heuristic, 6500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // but they do not come up often in practice. 6510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 6520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // TODO(keir): Pick a smarter number than the default above! In 6530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // theory a good choice is sqrt(eps) * x, which for doubles means 6540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // about 1e-8 * x. However, I have found this number too 6550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // optimistic. This number should be exposed for users to change. 6560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double numeric_derivative_relative_step_size; 6570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // If true, the user's parameter blocks are updated at the end of 6590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // every Minimizer iteration, otherwise they are updated when the 6600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Minimizer terminates. This is useful if, for example, the user 6610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // wishes to visualize the state of the optimization every 6620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // iteration. 6630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong bool update_state_every_iteration; 6640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Callbacks that are executed at the end of each iteration of the 6660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Minimizer. An iteration may terminate midway, either due to 6670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // numerical failures or because one of the convergence tests has 6680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // been satisfied. In this case none of the callbacks are 6690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // executed. 6700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Callbacks are executed in the order that they are specified in 6720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // this vector. By default, parameter blocks are updated only at 6730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the end of the optimization, i.e when the Minimizer 6740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // terminates. This behaviour is controlled by 6750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // update_state_every_variable. If the user wishes to have access 6760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // to the update parameter blocks when his/her callbacks are 6770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // executed, then set update_state_every_iteration to true. 6780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 6790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The solver does NOT take ownership of these pointers. 6800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong vector<IterationCallback*> callbacks; 6810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // If non-empty, a summary of the execution of the solver is 6830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // recorded to this file. 6840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong string solver_log; 6850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong }; 6860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong struct Summary { 6880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Summary(); 6890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // A brief one line description of the state of the solver after 6910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // termination. 6920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong string BriefReport() const; 6930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // A full multiline description of the state of the solver after 6950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // termination. 6960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong string FullReport() const; 6970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Minimizer summary ------------------------------------------------- 6991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling MinimizerType minimizer_type; 7001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong SolverTerminationType termination_type; 7020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // If the solver did not run, or there was a failure, a 7040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // description of the error. 7050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong string error; 7060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Cost of the problem before and after the optimization. See 7080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // problem.h for definition of the cost of a problem. 7090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double initial_cost; 7100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double final_cost; 7110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The part of the total cost that comes from residual blocks that 7130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // were held fixed by the preprocessor because all the parameter 7140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // blocks that they depend on were fixed. 7150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double fixed_cost; 7160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong vector<IterationSummary> iterations; 7180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_successful_steps; 7200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_unsuccessful_steps; 7211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int num_inner_iteration_steps; 7221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // All times reported below are wall times. 7240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // When the user calls Solve, before the actual optimization 7260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // occurs, Ceres performs a number of preprocessing steps. These 7270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // include error checks, memory allocations, and reorderings. This 7280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // time is accounted for as preprocessing time. 7290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double preprocessor_time_in_seconds; 7300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Time spent in the TrustRegionMinimizer. 7320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double minimizer_time_in_seconds; 7330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // After the Minimizer is finished, some time is spent in 7350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // re-evaluating residuals etc. This time is accounted for in the 7360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // postprocessor time. 7370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double postprocessor_time_in_seconds; 7380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Some total of all time spent inside Ceres when Solve is called. 7400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double total_time_in_seconds; 7410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double linear_solver_time_in_seconds; 7431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double residual_evaluation_time_in_seconds; 7441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double jacobian_evaluation_time_in_seconds; 7451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double inner_iteration_time_in_seconds; 7461d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Preprocessor summary. 7480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_parameter_blocks; 7490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_parameters; 7501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int num_effective_parameters; 7510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_residual_blocks; 7520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_residuals; 7530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_parameter_blocks_reduced; 7550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_parameters_reduced; 7561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int num_effective_parameters_reduced; 7570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_residual_blocks_reduced; 7580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_residuals_reduced; 7590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_eliminate_blocks_given; 7610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_eliminate_blocks_used; 7620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_threads_given; 7640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_threads_used; 7650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_linear_solver_threads_given; 7670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_linear_solver_threads_used; 7680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong LinearSolverType linear_solver_type_given; 7700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong LinearSolverType linear_solver_type_used; 7710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling vector<int> linear_solver_ordering_given; 7731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling vector<int> linear_solver_ordering_used; 7741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bool inner_iterations_given; 7761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bool inner_iterations_used; 7771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling vector<int> inner_iteration_ordering_given; 7791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling vector<int> inner_iteration_ordering_used; 7801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong PreconditionerType preconditioner_type; 7820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong TrustRegionStrategyType trust_region_strategy_type; 7840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong DoglegType dogleg_type; 7851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong SparseLinearAlgebraLibraryType sparse_linear_algebra_library; 7871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchDirectionType line_search_direction_type; 7891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchType line_search_type; 7901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchInterpolationType line_search_interpolation_type; 7911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling NonlinearConjugateGradientType nonlinear_conjugate_gradient_type; 7921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int max_lbfgs_rank; 7940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong }; 7950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Once a least squares problem has been built, this function takes 7970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the problem and optimizes it based on the values of the options 7980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // parameters. Upon return, a detailed summary of the work performed 7990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // by the preprocessor, the non-linear minmizer and the linear 8000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // solver are reported in the summary object. 8010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual void Solve(const Options& options, 8020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Problem* problem, 8030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Solver::Summary* summary); 8040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong}; 8050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 8060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Helper function which avoids going through the interface. 8070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongvoid Solve(const Solver::Options& options, 8080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Problem* problem, 8090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Solver::Summary* summary); 8100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 8110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} // namespace ceres 8120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 8130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#endif // CERES_PUBLIC_SOLVER_H_ 814