10ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Ceres Solver - A fast non-linear least squares minimizer 279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// Copyright 2014 Google Inc. All rights reserved. 30ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// http://code.google.com/p/ceres-solver/ 40ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 50ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Redistribution and use in source and binary forms, with or without 60ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// modification, are permitted provided that the following conditions are met: 70ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 80ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Redistributions of source code must retain the above copyright notice, 90ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// this list of conditions and the following disclaimer. 100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Redistributions in binary form must reproduce the above copyright notice, 110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// this list of conditions and the following disclaimer in the documentation 120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// and/or other materials provided with the distribution. 130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Neither the name of Google Inc. nor the names of its contributors may be 140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// used to endorse or promote products derived from this software without 150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// specific prior written permission. 160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// POSSIBILITY OF SUCH DAMAGE. 280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Author: keir@google.com (Keir Mierle) 300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/solver_impl.h" 320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include <cstdio> 340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include <iostream> // NOLINT 350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include <numeric> 361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include <string> 3779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez#include "ceres/array_utils.h" 3879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez#include "ceres/callbacks.h" 390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/coordinate_descent_minimizer.h" 401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/cxsparse.h" 410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/evaluator.h" 420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/gradient_checking_cost_function.h" 430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/iteration_callback.h" 440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/levenberg_marquardt_strategy.h" 451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/line_search_minimizer.h" 460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/linear_solver.h" 470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/map_util.h" 480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/minimizer.h" 490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/ordered_groups.h" 500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/parameter_block.h" 510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/parameter_block_ordering.h" 5279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez#include "ceres/preconditioner.h" 530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/problem.h" 540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/problem_impl.h" 550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/program.h" 5679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez#include "ceres/reorder_program.h" 570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/residual_block.h" 580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/stringprintf.h" 591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/suitesparse.h" 6079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez#include "ceres/summary_utils.h" 610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/trust_region_minimizer.h" 620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/wall_time.h" 630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongnamespace ceres { 650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongnamespace internal { 660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingvoid SolverImpl::TrustRegionMinimize( 681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const Solver::Options& options, 691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Program* program, 701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling CoordinateDescentMinimizer* inner_iteration_minimizer, 711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Evaluator* evaluator, 721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LinearSolver* linear_solver, 731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Solver::Summary* summary) { 740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Minimizer::Options minimizer_options(options); 7579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez minimizer_options.is_constrained = program->IsBoundsConstrained(); 760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // The optimizer works on contiguous parameter vectors; allocate 7879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // some. 7979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez Vector parameters(program->NumParameters()); 8079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 8179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // Collect the discontiguous parameters into a contiguous state 8279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // vector. 8379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez program->ParameterBlocksToStateVector(parameters.data()); 840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 8579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LoggingCallback logging_callback(TRUST_REGION, 8679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez options.minimizer_progress_to_stdout); 870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (options.logging_type != SILENT) { 880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong minimizer_options.callbacks.insert(minimizer_options.callbacks.begin(), 890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong &logging_callback); 900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 9279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez StateUpdatingCallback updating_callback(program, parameters.data()); 930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (options.update_state_every_iteration) { 940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // This must get pushed to the front of the callbacks so that it is run 950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // before any of the user callbacks. 960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong minimizer_options.callbacks.insert(minimizer_options.callbacks.begin(), 970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong &updating_callback); 980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong minimizer_options.evaluator = evaluator; 1010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong scoped_ptr<SparseMatrix> jacobian(evaluator->CreateJacobian()); 1021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong minimizer_options.jacobian = jacobian.get(); 1040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong minimizer_options.inner_iteration_minimizer = inner_iteration_minimizer; 1050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong TrustRegionStrategy::Options trust_region_strategy_options; 1070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong trust_region_strategy_options.linear_solver = linear_solver; 1080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong trust_region_strategy_options.initial_radius = 1090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong options.initial_trust_region_radius; 1100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong trust_region_strategy_options.max_radius = options.max_trust_region_radius; 1111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling trust_region_strategy_options.min_lm_diagonal = options.min_lm_diagonal; 1121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling trust_region_strategy_options.max_lm_diagonal = options.max_lm_diagonal; 1130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong trust_region_strategy_options.trust_region_strategy_type = 1140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong options.trust_region_strategy_type; 1150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong trust_region_strategy_options.dogleg_type = options.dogleg_type; 1160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong scoped_ptr<TrustRegionStrategy> strategy( 1170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong TrustRegionStrategy::Create(trust_region_strategy_options)); 1180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong minimizer_options.trust_region_strategy = strategy.get(); 1190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong TrustRegionMinimizer minimizer; 1210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double minimizer_start_time = WallTimeInSeconds(); 12279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez minimizer.Minimize(minimizer_options, parameters.data(), summary); 12379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 12479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // If the user aborted mid-optimization or the optimization 12579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // terminated because of a numerical failure, then do not update 12679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // user state. 12779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (summary->termination_type != USER_FAILURE && 12879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->termination_type != FAILURE) { 12979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez program->StateVectorToParameterBlocks(parameters.data()); 13079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez program->CopyParameterBlockStateToUserState(); 13179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez } 13279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 1330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong summary->minimizer_time_in_seconds = 1340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong WallTimeInSeconds() - minimizer_start_time; 1350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 1360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingvoid SolverImpl::LineSearchMinimize( 1381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const Solver::Options& options, 1391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Program* program, 1401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Evaluator* evaluator, 1411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Solver::Summary* summary) { 1421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Minimizer::Options minimizer_options(options); 1431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 14479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // The optimizer works on contiguous parameter vectors; allocate some. 14579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez Vector parameters(program->NumParameters()); 14679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 14779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // Collect the discontiguous parameters into a contiguous state vector. 14879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez program->ParameterBlocksToStateVector(parameters.data()); 1491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 15079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LoggingCallback logging_callback(LINE_SEARCH, 15179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez options.minimizer_progress_to_stdout); 1521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (options.logging_type != SILENT) { 1531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling minimizer_options.callbacks.insert(minimizer_options.callbacks.begin(), 1541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling &logging_callback); 1551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 1561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 15779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez StateUpdatingCallback updating_callback(program, parameters.data()); 1581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (options.update_state_every_iteration) { 1591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // This must get pushed to the front of the callbacks so that it is run 1601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // before any of the user callbacks. 1611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling minimizer_options.callbacks.insert(minimizer_options.callbacks.begin(), 1621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling &updating_callback); 1631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 1641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling minimizer_options.evaluator = evaluator; 1661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchMinimizer minimizer; 1681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double minimizer_start_time = WallTimeInSeconds(); 16979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez minimizer.Minimize(minimizer_options, parameters.data(), summary); 17079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 17179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // If the user aborted mid-optimization or the optimization 17279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // terminated because of a numerical failure, then do not update 17379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // user state. 17479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (summary->termination_type != USER_FAILURE && 17579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->termination_type != FAILURE) { 17679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez program->StateVectorToParameterBlocks(parameters.data()); 17779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez program->CopyParameterBlockStateToUserState(); 17879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez } 17979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 1801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->minimizer_time_in_seconds = 1811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling WallTimeInSeconds() - minimizer_start_time; 1821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} 1831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingvoid SolverImpl::Solve(const Solver::Options& options, 1851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ProblemImpl* problem_impl, 1860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Solver::Summary* summary) { 187399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger VLOG(2) << "Initial problem: " 188399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger << problem_impl->NumParameterBlocks() 189399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger << " parameter blocks, " 190399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger << problem_impl->NumParameters() 191399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger << " parameters, " 192399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger << problem_impl->NumResidualBlocks() 193399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger << " residual blocks, " 194399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger << problem_impl->NumResiduals() 195399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger << " residuals."; 1961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (options.minimizer_type == TRUST_REGION) { 1971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling TrustRegionSolve(options, problem_impl, summary); 1981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } else { 1991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchSolve(options, problem_impl, summary); 2001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 2011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} 2021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingvoid SolverImpl::TrustRegionSolve(const Solver::Options& original_options, 2041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ProblemImpl* original_problem_impl, 2051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Solver::Summary* summary) { 2061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling EventLogger event_logger("TrustRegionSolve"); 2070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double solver_start_time = WallTimeInSeconds(); 2080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Program* original_program = original_problem_impl->mutable_program(); 2100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ProblemImpl* problem_impl = original_problem_impl; 2110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->minimizer_type = TRUST_REGION; 2131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 21479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez SummarizeGivenProgram(*original_program, summary); 21579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez OrderingToGroupSizes(original_options.linear_solver_ordering.get(), 21679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez &(summary->linear_solver_ordering_given)); 21779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez OrderingToGroupSizes(original_options.inner_iteration_ordering.get(), 21879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez &(summary->inner_iteration_ordering_given)); 2191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Solver::Options options(original_options); 2210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#ifndef CERES_USE_OPENMP 2230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (options.num_threads > 1) { 2240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong LOG(WARNING) 2250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << "OpenMP support is not compiled into this binary; " 2260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << "only options.num_threads=1 is supported. Switching " 2270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << "to single threaded mode."; 2280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong options.num_threads = 1; 2290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 2300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (options.num_linear_solver_threads > 1) { 2310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong LOG(WARNING) 2320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << "OpenMP support is not compiled into this binary; " 2330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << "only options.num_linear_solver_threads=1 is supported. Switching " 2340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << "to single threaded mode."; 2350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong options.num_linear_solver_threads = 1; 2360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 2370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#endif 2380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong summary->num_threads_given = original_options.num_threads; 2400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong summary->num_threads_used = options.num_threads; 2410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (options.trust_region_minimizer_iterations_to_dump.size() > 0 && 2431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.trust_region_problem_dump_format_type != CONSOLE && 2441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.trust_region_problem_dump_directory.empty()) { 24579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->message = 2461d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "Solver::Options::trust_region_problem_dump_directory is empty."; 24779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG(ERROR) << summary->message; 24879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez return; 24979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez } 25079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 25179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (!original_program->ParameterBlocksAreFinite(&summary->message)) { 25279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG(ERROR) << "Terminating: " << summary->message; 25379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez return; 25479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez } 25579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 25679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (!original_program->IsFeasible(&summary->message)) { 25779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG(ERROR) << "Terminating: " << summary->message; 2580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return; 2590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 2600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling event_logger.AddEvent("Init"); 2621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong original_program->SetParameterBlockStatePtrsToUserStatePtrs(); 2641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling event_logger.AddEvent("SetParameterBlockPtrs"); 2650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // If the user requests gradient checking, construct a new 2670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // ProblemImpl by wrapping the CostFunctions of problem_impl inside 2680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // GradientCheckingCostFunction and replacing problem_impl with 2690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // gradient_checking_problem_impl. 2700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong scoped_ptr<ProblemImpl> gradient_checking_problem_impl; 2710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (options.check_gradients) { 2720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong VLOG(1) << "Checking Gradients"; 2730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong gradient_checking_problem_impl.reset( 2740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong CreateGradientCheckingProblemImpl( 2750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong problem_impl, 2760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong options.numeric_derivative_relative_step_size, 2770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong options.gradient_check_relative_precision)); 2780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // From here on, problem_impl will point to the gradient checking 2800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // version. 2810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong problem_impl = gradient_checking_problem_impl.get(); 2820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 2830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 28479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (options.linear_solver_ordering.get() != NULL) { 28579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (!IsOrderingValid(options, problem_impl, &summary->message)) { 28679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG(ERROR) << summary->message; 2870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return; 2880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 2891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling event_logger.AddEvent("CheckOrdering"); 2900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } else { 29179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez options.linear_solver_ordering.reset(new ParameterBlockOrdering); 2920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const ProblemImpl::ParameterMap& parameter_map = 2930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong problem_impl->parameter_map(); 2940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong for (ProblemImpl::ParameterMap::const_iterator it = parameter_map.begin(); 2950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong it != parameter_map.end(); 2960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ++it) { 2970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong options.linear_solver_ordering->AddElementToGroup(it->first, 0); 2980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 2991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling event_logger.AddEvent("ConstructOrdering"); 3000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Create the three objects needed to minimize: the transformed program, the 3030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // evaluator, and the linear solver. 3040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong scoped_ptr<Program> reduced_program(CreateReducedProgram(&options, 3050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong problem_impl, 3060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong &summary->fixed_cost, 30779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez &summary->message)); 3081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 3091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling event_logger.AddEvent("CreateReducedProgram"); 3100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (reduced_program == NULL) { 3110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return; 3120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 31479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez OrderingToGroupSizes(options.linear_solver_ordering.get(), 31579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez &(summary->linear_solver_ordering_used)); 31679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez SummarizeReducedProgram(*reduced_program, summary); 3170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (summary->num_parameter_blocks_reduced == 0) { 3190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong summary->preprocessor_time_in_seconds = 3200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong WallTimeInSeconds() - solver_start_time; 3210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double post_process_start_time = WallTimeInSeconds(); 32379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 32479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->message = 32579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "Function tolerance reached. " 32679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "No non-constant parameter blocks found."; 32779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->termination_type = CONVERGENCE; 32879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez VLOG_IF(1, options.logging_type != SILENT) << summary->message; 3290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->initial_cost = summary->fixed_cost; 3311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->final_cost = summary->fixed_cost; 3321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 3330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Ensure the program state is set to the user parameters on the way out. 3340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong original_program->SetParameterBlockStatePtrsToUserStatePtrs(); 33579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez original_program->SetParameterOffsetsAndIndex(); 3360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong summary->postprocessor_time_in_seconds = 3380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong WallTimeInSeconds() - post_process_start_time; 3390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return; 3400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong scoped_ptr<LinearSolver> 34379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez linear_solver(CreateLinearSolver(&options, &summary->message)); 3441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling event_logger.AddEvent("CreateLinearSolver"); 3450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (linear_solver == NULL) { 3460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return; 3470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong summary->linear_solver_type_given = original_options.linear_solver_type; 3500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong summary->linear_solver_type_used = options.linear_solver_type; 3510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong summary->preconditioner_type = options.preconditioner_type; 35379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->visibility_clustering_type = options.visibility_clustering_type; 3540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong summary->num_linear_solver_threads_given = 3560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong original_options.num_linear_solver_threads; 3570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong summary->num_linear_solver_threads_used = options.num_linear_solver_threads; 3580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 359399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger summary->dense_linear_algebra_library_type = 360399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger options.dense_linear_algebra_library_type; 361399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger summary->sparse_linear_algebra_library_type = 362399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger options.sparse_linear_algebra_library_type; 3630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong summary->trust_region_strategy_type = options.trust_region_strategy_type; 3650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong summary->dogleg_type = options.dogleg_type; 3660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong scoped_ptr<Evaluator> evaluator(CreateEvaluator(options, 3680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong problem_impl->parameter_map(), 3690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong reduced_program.get(), 37079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez &summary->message)); 3711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 3721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling event_logger.AddEvent("CreateEvaluator"); 3731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 3740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (evaluator == NULL) { 3750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return; 3760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong scoped_ptr<CoordinateDescentMinimizer> inner_iteration_minimizer; 3790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (options.use_inner_iterations) { 3800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (reduced_program->parameter_blocks().size() < 2) { 3810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong LOG(WARNING) << "Reduced problem only contains one parameter block." 3820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << "Disabling inner iterations."; 3830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } else { 3840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong inner_iteration_minimizer.reset( 38579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez CreateInnerIterationMinimizer(options, 3860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong *reduced_program, 3870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong problem_impl->parameter_map(), 3881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary)); 3890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (inner_iteration_minimizer == NULL) { 39079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG(ERROR) << summary->message; 3910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return; 3920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling event_logger.AddEvent("CreateInnerIterationMinimizer"); 3960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double minimizer_start_time = WallTimeInSeconds(); 3980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong summary->preprocessor_time_in_seconds = 3990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong minimizer_start_time - solver_start_time; 4000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 4010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Run the optimization. 4021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling TrustRegionMinimize(options, 4031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling reduced_program.get(), 4041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling inner_iteration_minimizer.get(), 4051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling evaluator.get(), 4061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling linear_solver.get(), 4071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary); 4081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling event_logger.AddEvent("Minimize"); 4091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double post_process_start_time = WallTimeInSeconds(); 4110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 41279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez SetSummaryFinalCost(summary); 4130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 4141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Ensure the program state is set to the user parameters on the way 4151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // out. 4161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling original_program->SetParameterBlockStatePtrsToUserStatePtrs(); 41779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez original_program->SetParameterOffsetsAndIndex(); 4181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const map<string, double>& linear_solver_time_statistics = 4201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling linear_solver->TimeStatistics(); 4211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->linear_solver_time_in_seconds = 4221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FindWithDefault(linear_solver_time_statistics, 4231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "LinearSolver::Solve", 4241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 0.0); 4251d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const map<string, double>& evaluator_time_statistics = 4271d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling evaluator->TimeStatistics(); 4281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->residual_evaluation_time_in_seconds = 4301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FindWithDefault(evaluator_time_statistics, "Evaluator::Residual", 0.0); 4311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->jacobian_evaluation_time_in_seconds = 4321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FindWithDefault(evaluator_time_statistics, "Evaluator::Jacobian", 0.0); 4331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Stick a fork in it, we're done. 4351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->postprocessor_time_in_seconds = 4361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling WallTimeInSeconds() - post_process_start_time; 4371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling event_logger.AddEvent("PostProcess"); 4381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} 4391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingvoid SolverImpl::LineSearchSolve(const Solver::Options& original_options, 4411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ProblemImpl* original_problem_impl, 4421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Solver::Summary* summary) { 4431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double solver_start_time = WallTimeInSeconds(); 4440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 4451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Program* original_program = original_problem_impl->mutable_program(); 4461d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ProblemImpl* problem_impl = original_problem_impl; 4471d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 44879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez SummarizeGivenProgram(*original_program, summary); 4491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->minimizer_type = LINE_SEARCH; 4501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->line_search_direction_type = 4511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling original_options.line_search_direction_type; 4521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->max_lbfgs_rank = original_options.max_lbfgs_rank; 4531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->line_search_type = original_options.line_search_type; 4541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->line_search_interpolation_type = 4551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling original_options.line_search_interpolation_type; 4561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->nonlinear_conjugate_gradient_type = 4571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling original_options.nonlinear_conjugate_gradient_type; 4581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 45979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (original_program->IsBoundsConstrained()) { 46079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->message = "LINE_SEARCH Minimizer does not support bounds."; 46179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG(ERROR) << "Terminating: " << summary->message; 4621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return; 4631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 4641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Solver::Options options(original_options); 4661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // This ensures that we get a Block Jacobian Evaluator along with 4681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // none of the Schur nonsense. This file will have to be extensively 4691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // refactored to deal with the various bits of cleanups related to 4701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // line search. 4711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.linear_solver_type = CGNR; 4721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#ifndef CERES_USE_OPENMP 4751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (options.num_threads > 1) { 4761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LOG(WARNING) 4771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << "OpenMP support is not compiled into this binary; " 4781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << "only options.num_threads=1 is supported. Switching " 4791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << "to single threaded mode."; 4801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.num_threads = 1; 4811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 4821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#endif // CERES_USE_OPENMP 4831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->num_threads_given = original_options.num_threads; 4851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->num_threads_used = options.num_threads; 4861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 48779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (!original_program->ParameterBlocksAreFinite(&summary->message)) { 48879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG(ERROR) << "Terminating: " << summary->message; 48979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez return; 49079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez } 49179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 49279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (options.linear_solver_ordering.get() != NULL) { 49379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (!IsOrderingValid(options, problem_impl, &summary->message)) { 49479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG(ERROR) << summary->message; 4951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return; 4961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 4971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } else { 49879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez options.linear_solver_ordering.reset(new ParameterBlockOrdering); 4991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const ProblemImpl::ParameterMap& parameter_map = 5001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling problem_impl->parameter_map(); 5011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling for (ProblemImpl::ParameterMap::const_iterator it = parameter_map.begin(); 5021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling it != parameter_map.end(); 5031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ++it) { 5041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.linear_solver_ordering->AddElementToGroup(it->first, 0); 5051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 5061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 5071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 50879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 5091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling original_program->SetParameterBlockStatePtrsToUserStatePtrs(); 5101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // If the user requests gradient checking, construct a new 5121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // ProblemImpl by wrapping the CostFunctions of problem_impl inside 5131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // GradientCheckingCostFunction and replacing problem_impl with 5141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // gradient_checking_problem_impl. 5151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling scoped_ptr<ProblemImpl> gradient_checking_problem_impl; 5161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (options.check_gradients) { 5171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling VLOG(1) << "Checking Gradients"; 5181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling gradient_checking_problem_impl.reset( 5191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling CreateGradientCheckingProblemImpl( 5201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling problem_impl, 5211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.numeric_derivative_relative_step_size, 5221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.gradient_check_relative_precision)); 5231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // From here on, problem_impl will point to the gradient checking 5251d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // version. 5261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling problem_impl = gradient_checking_problem_impl.get(); 5271d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 5281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Create the three objects needed to minimize: the transformed program, the 5301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // evaluator, and the linear solver. 5311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling scoped_ptr<Program> reduced_program(CreateReducedProgram(&options, 5321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling problem_impl, 5331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling &summary->fixed_cost, 53479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez &summary->message)); 5351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (reduced_program == NULL) { 5361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return; 5371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 5381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 53979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez SummarizeReducedProgram(*reduced_program, summary); 5401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (summary->num_parameter_blocks_reduced == 0) { 5411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->preprocessor_time_in_seconds = 5421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling WallTimeInSeconds() - solver_start_time; 5431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 54479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->message = 54579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "Function tolerance reached. " 54679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "No non-constant parameter blocks found."; 54779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->termination_type = CONVERGENCE; 54879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez VLOG_IF(1, options.logging_type != SILENT) << summary->message; 54979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->initial_cost = summary->fixed_cost; 55079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->final_cost = summary->fixed_cost; 5511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double post_process_start_time = WallTimeInSeconds(); 5531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling SetSummaryFinalCost(summary); 5541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Ensure the program state is set to the user parameters on the way out. 5561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling original_program->SetParameterBlockStatePtrsToUserStatePtrs(); 55779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez original_program->SetParameterOffsetsAndIndex(); 55879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 5591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->postprocessor_time_in_seconds = 5601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling WallTimeInSeconds() - post_process_start_time; 5611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return; 5621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 5631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling scoped_ptr<Evaluator> evaluator(CreateEvaluator(options, 5651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling problem_impl->parameter_map(), 5661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling reduced_program.get(), 56779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez &summary->message)); 5681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (evaluator == NULL) { 5691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return; 5701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 5711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double minimizer_start_time = WallTimeInSeconds(); 5731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->preprocessor_time_in_seconds = 5741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling minimizer_start_time - solver_start_time; 5751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Run the optimization. 57779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LineSearchMinimize(options, reduced_program.get(), evaluator.get(), summary); 5781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double post_process_start_time = WallTimeInSeconds(); 5801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling SetSummaryFinalCost(summary); 5821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Ensure the program state is set to the user parameters on the way out. 5840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong original_program->SetParameterBlockStatePtrsToUserStatePtrs(); 58579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez original_program->SetParameterOffsetsAndIndex(); 5860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 5871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const map<string, double>& evaluator_time_statistics = 5881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling evaluator->TimeStatistics(); 5891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->residual_evaluation_time_in_seconds = 5911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FindWithDefault(evaluator_time_statistics, "Evaluator::Residual", 0.0); 5921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->jacobian_evaluation_time_in_seconds = 5931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FindWithDefault(evaluator_time_statistics, "Evaluator::Jacobian", 0.0); 5941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Stick a fork in it, we're done. 5960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong summary->postprocessor_time_in_seconds = 5970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong WallTimeInSeconds() - post_process_start_time; 5980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 5990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongbool SolverImpl::IsOrderingValid(const Solver::Options& options, 6010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const ProblemImpl* problem_impl, 6020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong string* error) { 6030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (options.linear_solver_ordering->NumElements() != 6040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong problem_impl->NumParameterBlocks()) { 6050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong *error = "Number of parameter blocks in user supplied ordering " 6060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong "does not match the number of parameter blocks in the problem"; 6070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return false; 6080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 6090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const Program& program = problem_impl->program(); 6110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const vector<ParameterBlock*>& parameter_blocks = program.parameter_blocks(); 6120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong for (vector<ParameterBlock*>::const_iterator it = parameter_blocks.begin(); 6130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong it != parameter_blocks.end(); 6140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ++it) { 6150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (!options.linear_solver_ordering 6160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ->IsMember(const_cast<double*>((*it)->user_state()))) { 6170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong *error = "Problem contains a parameter block that is not in " 6180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong "the user specified ordering."; 6190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return false; 6200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 6210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 6220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (IsSchurType(options.linear_solver_type) && 6240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong options.linear_solver_ordering->NumGroups() > 1) { 6250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const vector<ResidualBlock*>& residual_blocks = program.residual_blocks(); 6260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const set<double*>& e_blocks = 6270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong options.linear_solver_ordering->group_to_elements().begin()->second; 6280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (!IsParameterBlockSetIndependent(e_blocks, residual_blocks)) { 6290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong *error = "The user requested the use of a Schur type solver. " 6300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong "But the first elimination group in the ordering is not an " 6310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong "independent set."; 6320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return false; 6330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 6340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 6350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return true; 6360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 6370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingbool SolverImpl::IsParameterBlockSetIndependent( 6391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const set<double*>& parameter_block_ptrs, 6401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const vector<ResidualBlock*>& residual_blocks) { 6410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Loop over each residual block and ensure that no two parameter 6420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // blocks in the same residual block are part of 6430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // parameter_block_ptrs as that would violate the assumption that it 6440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // is an independent set in the Hessian matrix. 6450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong for (vector<ResidualBlock*>::const_iterator it = residual_blocks.begin(); 6460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong it != residual_blocks.end(); 6470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ++it) { 6480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ParameterBlock* const* parameter_blocks = (*it)->parameter_blocks(); 6490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const int num_parameter_blocks = (*it)->NumParameterBlocks(); 6500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int count = 0; 6510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong for (int i = 0; i < num_parameter_blocks; ++i) { 6520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong count += parameter_block_ptrs.count( 6530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong parameter_blocks[i]->mutable_user_state()); 6540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 6550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (count > 1) { 6560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return false; 6570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 6580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 6590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return true; 6600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 6610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 6620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus KongProgram* SolverImpl::CreateReducedProgram(Solver::Options* options, 6630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ProblemImpl* problem_impl, 6640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double* fixed_cost, 6650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong string* error) { 66679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez CHECK_NOTNULL(options->linear_solver_ordering.get()); 6670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Program* original_program = problem_impl->mutable_program(); 6680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 66979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez vector<double*> removed_parameter_blocks; 67079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez scoped_ptr<Program> reduced_program( 67179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez original_program->CreateReducedProgram(&removed_parameter_blocks, 67279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez fixed_cost, 67379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez error)); 67479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (reduced_program.get() == NULL) { 6750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return NULL; 6760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 6770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 678399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger VLOG(2) << "Reduced problem: " 67979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << reduced_program->NumParameterBlocks() 680399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger << " parameter blocks, " 68179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << reduced_program->NumParameters() 682399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger << " parameters, " 68379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << reduced_program->NumResidualBlocks() 684399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger << " residual blocks, " 68579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << reduced_program->NumResiduals() 686399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger << " residuals."; 687399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger 68879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (reduced_program->NumParameterBlocks() == 0) { 6890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong LOG(WARNING) << "No varying parameter blocks to optimize; " 6900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << "bailing early."; 69179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez return reduced_program.release(); 69279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez } 69379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 69479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez ParameterBlockOrdering* linear_solver_ordering = 69579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez options->linear_solver_ordering.get(); 69679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez const int min_group_id = 69779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez linear_solver_ordering->MinNonZeroGroup(); 69879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez linear_solver_ordering->Remove(removed_parameter_blocks); 69979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 70079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez ParameterBlockOrdering* inner_iteration_ordering = 70179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez options->inner_iteration_ordering.get(); 70279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (inner_iteration_ordering != NULL) { 70379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez inner_iteration_ordering->Remove(removed_parameter_blocks); 7040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 7050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (IsSchurType(options->linear_solver_type) && 7071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling linear_solver_ordering->GroupSize(min_group_id) == 0) { 7081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // If the user requested the use of a Schur type solver, and 7091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // supplied a non-NULL linear_solver_ordering object with more than 7101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // one elimination group, then it can happen that after all the 7111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // parameter blocks which are fixed or unused have been removed from 7121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // the program and the ordering, there are no more parameter blocks 7131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // in the first elimination group. 7141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 7151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // In such a case, the use of a Schur type solver is not possible, 7161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // as they assume there is at least one e_block. Thus, we 7171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // automatically switch to the closest solver to the one indicated 7181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // by the user. 71979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (options->linear_solver_type == ITERATIVE_SCHUR) { 72079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez options->preconditioner_type = 72179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez Preconditioner::PreconditionerForZeroEBlocks( 72279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez options->preconditioner_type); 72379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez } 72479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 72579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez options->linear_solver_type = 72679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LinearSolver::LinearSolverForZeroEBlocks( 72779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez options->linear_solver_type); 7280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 7290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (IsSchurType(options->linear_solver_type)) { 7311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (!ReorderProgramForSchurTypeLinearSolver( 7321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options->linear_solver_type, 733399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger options->sparse_linear_algebra_library_type, 7341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling problem_impl->parameter_map(), 7351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling linear_solver_ordering, 73679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez reduced_program.get(), 7371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling error)) { 7381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return NULL; 7391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 74079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez return reduced_program.release(); 7410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 7420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 74379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (options->linear_solver_type == SPARSE_NORMAL_CHOLESKY && 74479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez !options->dynamic_sparsity) { 7451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (!ReorderProgramForSparseNormalCholesky( 746399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger options->sparse_linear_algebra_library_type, 74779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez *linear_solver_ordering, 74879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez reduced_program.get(), 7491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling error)) { 7501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return NULL; 7510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 7520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 75379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez return reduced_program.release(); 7540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 7550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 75679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez reduced_program->SetParameterOffsetsAndIndex(); 75779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez return reduced_program.release(); 7580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 7590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus KongLinearSolver* SolverImpl::CreateLinearSolver(Solver::Options* options, 7610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong string* error) { 7620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong CHECK_NOTNULL(options); 76379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez CHECK_NOTNULL(options->linear_solver_ordering.get()); 7640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong CHECK_NOTNULL(error); 7650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 7660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (options->trust_region_strategy_type == DOGLEG) { 7670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (options->linear_solver_type == ITERATIVE_SCHUR || 7680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong options->linear_solver_type == CGNR) { 7690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong *error = "DOGLEG only supports exact factorization based linear " 7700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong "solvers. If you want to use an iterative solver please " 7710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong "use LEVENBERG_MARQUARDT as the trust_region_strategy_type"; 7720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return NULL; 7730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 7740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 7750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 776399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger#ifdef CERES_NO_LAPACK 777399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger if (options->linear_solver_type == DENSE_NORMAL_CHOLESKY && 778399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger options->dense_linear_algebra_library_type == LAPACK) { 779399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger *error = "Can't use DENSE_NORMAL_CHOLESKY with LAPACK because " 780399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger "LAPACK was not enabled when Ceres was built."; 781399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger return NULL; 782399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger } 783399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger 784399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger if (options->linear_solver_type == DENSE_QR && 785399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger options->dense_linear_algebra_library_type == LAPACK) { 786399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger *error = "Can't use DENSE_QR with LAPACK because " 787399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger "LAPACK was not enabled when Ceres was built."; 788399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger return NULL; 789399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger } 790399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger 791399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger if (options->linear_solver_type == DENSE_SCHUR && 792399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger options->dense_linear_algebra_library_type == LAPACK) { 793399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger *error = "Can't use DENSE_SCHUR with LAPACK because " 794399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger "LAPACK was not enabled when Ceres was built."; 795399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger return NULL; 796399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger } 797399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger#endif 798399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger 7990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#ifdef CERES_NO_SUITESPARSE 8000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (options->linear_solver_type == SPARSE_NORMAL_CHOLESKY && 801399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger options->sparse_linear_algebra_library_type == SUITE_SPARSE) { 8020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong *error = "Can't use SPARSE_NORMAL_CHOLESKY with SUITESPARSE because " 8030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong "SuiteSparse was not enabled when Ceres was built."; 8040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return NULL; 8050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 8060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 8070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (options->preconditioner_type == CLUSTER_JACOBI) { 8080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong *error = "CLUSTER_JACOBI preconditioner not suppored. Please build Ceres " 8090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong "with SuiteSparse support."; 8100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return NULL; 8110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 8120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 8130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (options->preconditioner_type == CLUSTER_TRIDIAGONAL) { 8140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong *error = "CLUSTER_TRIDIAGONAL preconditioner not suppored. Please build " 8150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong "Ceres with SuiteSparse support."; 8160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return NULL; 8170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 8180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#endif 8190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 8200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#ifdef CERES_NO_CXSPARSE 8210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (options->linear_solver_type == SPARSE_NORMAL_CHOLESKY && 822399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger options->sparse_linear_algebra_library_type == CX_SPARSE) { 8230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong *error = "Can't use SPARSE_NORMAL_CHOLESKY with CXSPARSE because " 8240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong "CXSparse was not enabled when Ceres was built."; 8250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return NULL; 8260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 8270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#endif 8280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 8291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (options->max_linear_solver_iterations <= 0) { 8301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *error = "Solver::Options::max_linear_solver_iterations is not positive."; 8310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return NULL; 8320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 8331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (options->min_linear_solver_iterations <= 0) { 8341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *error = "Solver::Options::min_linear_solver_iterations is not positive."; 8350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return NULL; 8360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 8371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (options->min_linear_solver_iterations > 8381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options->max_linear_solver_iterations) { 8391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *error = "Solver::Options::min_linear_solver_iterations > " 8401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "Solver::Options::max_linear_solver_iterations."; 8410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return NULL; 8420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 8430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 8440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong LinearSolver::Options linear_solver_options; 8450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong linear_solver_options.min_num_iterations = 8461d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options->min_linear_solver_iterations; 8470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong linear_solver_options.max_num_iterations = 8481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options->max_linear_solver_iterations; 8490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong linear_solver_options.type = options->linear_solver_type; 8500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong linear_solver_options.preconditioner_type = options->preconditioner_type; 85179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez linear_solver_options.visibility_clustering_type = 85279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez options->visibility_clustering_type; 853399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger linear_solver_options.sparse_linear_algebra_library_type = 854399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger options->sparse_linear_algebra_library_type; 855399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger linear_solver_options.dense_linear_algebra_library_type = 856399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger options->dense_linear_algebra_library_type; 8571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling linear_solver_options.use_postordering = options->use_postordering; 85879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez linear_solver_options.dynamic_sparsity = options->dynamic_sparsity; 8590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 8601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Ignore user's postordering preferences and force it to be true if 8611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // cholmod_camd is not available. This ensures that the linear 8621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // solver does not assume that a fill-reducing pre-ordering has been 8631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // done. 8641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#if !defined(CERES_NO_SUITESPARSE) && defined(CERES_NO_CAMD) 8651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (IsSchurType(linear_solver_options.type) && 866399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger options->sparse_linear_algebra_library_type == SUITE_SPARSE) { 8671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling linear_solver_options.use_postordering = true; 8680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 8691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#endif 8701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 8711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling linear_solver_options.num_threads = options->num_linear_solver_threads; 8720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong options->num_linear_solver_threads = linear_solver_options.num_threads; 8730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 87479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez OrderingToGroupSizes(options->linear_solver_ordering.get(), 87579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez &linear_solver_options.elimination_groups); 8760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Schur type solvers, expect at least two elimination groups. If 8770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // there is only one elimination group, then CreateReducedProgram 8780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // guarantees that this group only contains e_blocks. Thus we add a 8790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // dummy elimination group with zero blocks in it. 8800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (IsSchurType(linear_solver_options.type) && 8810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong linear_solver_options.elimination_groups.size() == 1) { 8820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong linear_solver_options.elimination_groups.push_back(0); 8830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 8840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 8850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return LinearSolver::Create(linear_solver_options); 8860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 8870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 8881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha HaeberlingEvaluator* SolverImpl::CreateEvaluator( 8891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const Solver::Options& options, 8901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const ProblemImpl::ParameterMap& parameter_map, 8911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Program* program, 8921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling string* error) { 8930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Evaluator::Options evaluator_options; 8940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong evaluator_options.linear_solver_type = options.linear_solver_type; 8950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong evaluator_options.num_eliminate_blocks = 8960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong (options.linear_solver_ordering->NumGroups() > 0 && 8970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsSchurType(options.linear_solver_type)) 8980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ? (options.linear_solver_ordering 8990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ->group_to_elements().begin() 9000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ->second.size()) 9010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong : 0; 9020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong evaluator_options.num_threads = options.num_threads; 90379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez evaluator_options.dynamic_sparsity = options.dynamic_sparsity; 9040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return Evaluator::Create(evaluator_options, program, error); 9050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 9060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 9070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus KongCoordinateDescentMinimizer* SolverImpl::CreateInnerIterationMinimizer( 9080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const Solver::Options& options, 9090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const Program& program, 9100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const ProblemImpl::ParameterMap& parameter_map, 9111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Solver::Summary* summary) { 9121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->inner_iterations_given = true; 9131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 9140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong scoped_ptr<CoordinateDescentMinimizer> inner_iteration_minimizer( 9150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong new CoordinateDescentMinimizer); 9160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong scoped_ptr<ParameterBlockOrdering> inner_iteration_ordering; 9170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ParameterBlockOrdering* ordering_ptr = NULL; 9180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 91979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (options.inner_iteration_ordering.get() == NULL) { 92079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez inner_iteration_ordering.reset( 92179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez CoordinateDescentMinimizer::CreateOrdering(program)); 9220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ordering_ptr = inner_iteration_ordering.get(); 9230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } else { 92479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez ordering_ptr = options.inner_iteration_ordering.get(); 92579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (!CoordinateDescentMinimizer::IsOrderingValid(program, 92679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez *ordering_ptr, 92779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez &summary->message)) { 92879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez return NULL; 9290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 9300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 9310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 9320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (!inner_iteration_minimizer->Init(program, 9330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong parameter_map, 9340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong *ordering_ptr, 93579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez &summary->message)) { 9360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return NULL; 9370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 9380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 9391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->inner_iterations_used = true; 9401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->inner_iteration_time_in_seconds = 0.0; 94179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez OrderingToGroupSizes(ordering_ptr, 94279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez &(summary->inner_iteration_ordering_used)); 9430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return inner_iteration_minimizer.release(); 9440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 9450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 9460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} // namespace internal 9470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} // namespace ceres 948