11d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// Ceres Solver - A fast non-linear least squares minimizer 21d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// Copyright 2012 Google Inc. All rights reserved. 31d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// http://code.google.com/p/ceres-solver/ 41d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// 51d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// Redistribution and use in source and binary forms, with or without 61d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// modification, are permitted provided that the following conditions are met: 71d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// 81d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// * Redistributions of source code must retain the above copyright notice, 91d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// this list of conditions and the following disclaimer. 101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// * Redistributions in binary form must reproduce the above copyright notice, 111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// this list of conditions and the following disclaimer in the documentation 121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// and/or other materials provided with the distribution. 131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// * Neither the name of Google Inc. nor the names of its contributors may be 141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// used to endorse or promote products derived from this software without 151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// specific prior written permission. 161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// 171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 251d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 271d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// POSSIBILITY OF SUCH DAMAGE. 281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// 291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// Author: sameeragarwal@google.com (Sameer Agarwal) 301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// 311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// Generic loop for line search based optimization algorithms. 321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// 331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// This is primarily inpsired by the minFunc packaged written by Mark 341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// Schmidt. 351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// 361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// http://www.di.ens.fr/~mschmidt/Software/minFunc.html 371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// 381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// For details on the theory and implementation see "Numerical 391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// Optimization" by Nocedal & Wright. 401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/line_search_minimizer.h" 421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include <algorithm> 441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include <cstdlib> 451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include <cmath> 461d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include <string> 471d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include <vector> 481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "Eigen/Dense" 501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/array_utils.h" 511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/evaluator.h" 521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/internal/eigen.h" 531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/internal/port.h" 541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/internal/scoped_ptr.h" 551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/line_search.h" 561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/line_search_direction.h" 571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/stringprintf.h" 581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/types.h" 591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/wall_time.h" 601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "glog/logging.h" 611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingnamespace ceres { 631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingnamespace internal { 641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingnamespace { 651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 6679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// TODO(sameeragarwal): I think there is a small bug here, in that if 6779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// the evaluation fails, then the state can contain garbage. Look at 6879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// this more carefully. 691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingbool Evaluate(Evaluator* evaluator, 701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const Vector& x, 7179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LineSearchMinimizer::State* state, 7279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez string* message) { 7379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (!evaluator->Evaluate(x.data(), 7479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez &(state->cost), 7579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez NULL, 7679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez state->gradient.data(), 7779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez NULL)) { 7879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez *message = "Gradient evaluation failed."; 7979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez return false; 8079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez } 8179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 8279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez Vector negative_gradient = -state->gradient; 8379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez Vector projected_gradient_step(x.size()); 8479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (!evaluator->Plus(x.data(), 8579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez negative_gradient.data(), 8679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez projected_gradient_step.data())) { 8779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez *message = "projected_gradient_step = Plus(x, -gradient) failed."; 8879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez return false; 891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 9179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez state->gradient_squared_norm = (x - projected_gradient_step).squaredNorm(); 9279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez state->gradient_max_norm = 9379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez (x - projected_gradient_step).lpNorm<Eigen::Infinity>(); 9479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez return true; 951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} 961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} // namespace 981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingvoid LineSearchMinimizer::Minimize(const Minimizer::Options& options, 1001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double* parameters, 1011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Solver::Summary* summary) { 10279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez const bool is_not_silent = !options.is_silent; 1031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double start_time = WallTimeInSeconds(); 1041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double iteration_start_time = start_time; 1051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Evaluator* evaluator = CHECK_NOTNULL(options.evaluator); 1071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const int num_parameters = evaluator->NumParameters(); 1081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const int num_effective_parameters = evaluator->NumEffectiveParameters(); 1091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->termination_type = NO_CONVERGENCE; 1111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->num_successful_steps = 0; 1121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->num_unsuccessful_steps = 0; 1131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling VectorRef x(parameters, num_parameters); 1151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling State current_state(num_parameters, num_effective_parameters); 1171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling State previous_state(num_parameters, num_effective_parameters); 1181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Vector delta(num_effective_parameters); 1201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Vector x_plus_delta(num_parameters); 1211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling IterationSummary iteration_summary; 1231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.iteration = 0; 1241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.step_is_valid = false; 1251d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.step_is_successful = false; 1261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.cost_change = 0.0; 1271d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.gradient_max_norm = 0.0; 12879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez iteration_summary.gradient_norm = 0.0; 1291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.step_norm = 0.0; 1301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.linear_solver_iterations = 0; 1311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.step_solver_time_in_seconds = 0; 1321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Do initial cost and Jacobian evaluation. 13479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (!Evaluate(evaluator, x, ¤t_state, &summary->message)) { 13579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->termination_type = FAILURE; 13679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->message = "Initial cost and jacobian evaluation failed. " 13779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "More details: " + summary->message; 13879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG_IF(WARNING, is_not_silent) << "Terminating: " << summary->message; 1391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return; 1401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 1411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->initial_cost = current_state.cost + summary->fixed_cost; 1431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.cost = current_state.cost + summary->fixed_cost; 1441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.gradient_max_norm = current_state.gradient_max_norm; 14679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez iteration_summary.gradient_norm = sqrt(current_state.gradient_squared_norm); 14779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 14879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (iteration_summary.gradient_max_norm <= options.gradient_tolerance) { 14979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->message = StringPrintf("Gradient tolerance reached. " 15079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "Gradient max norm: %e <= %e", 15179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez iteration_summary.gradient_max_norm, 15279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez options.gradient_tolerance); 15379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->termination_type = CONVERGENCE; 15479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message; 1551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return; 1561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 1571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.iteration_time_in_seconds = 1591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling WallTimeInSeconds() - iteration_start_time; 1601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.cumulative_time_in_seconds = 1611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling WallTimeInSeconds() - start_time 1621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling + summary->preprocessor_time_in_seconds; 1631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->iterations.push_back(iteration_summary); 1641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchDirection::Options line_search_direction_options; 1661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_direction_options.num_parameters = num_effective_parameters; 1671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_direction_options.type = options.line_search_direction_type; 1681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_direction_options.nonlinear_conjugate_gradient_type = 1691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.nonlinear_conjugate_gradient_type; 1701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_direction_options.max_lbfgs_rank = options.max_lbfgs_rank; 1711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_direction_options.use_approximate_eigenvalue_bfgs_scaling = 1721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.use_approximate_eigenvalue_bfgs_scaling; 1731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling scoped_ptr<LineSearchDirection> line_search_direction( 1741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchDirection::Create(line_search_direction_options)); 1751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchFunction line_search_function(evaluator); 1771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearch::Options line_search_options; 1791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_options.interpolation_type = 1801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.line_search_interpolation_type; 1811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_options.min_step_size = options.min_line_search_step_size; 1821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_options.sufficient_decrease = 1831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.line_search_sufficient_function_decrease; 1841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_options.max_step_contraction = 1851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.max_line_search_step_contraction; 1861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_options.min_step_contraction = 1871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.min_line_search_step_contraction; 1881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_options.max_num_iterations = 1891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.max_num_line_search_step_size_iterations; 1901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_options.sufficient_curvature_decrease = 1911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.line_search_sufficient_curvature_decrease; 1921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_options.max_step_expansion = 1931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.max_line_search_step_expansion; 1941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_options.function = &line_search_function; 1951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling scoped_ptr<LineSearch> 1971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search(LineSearch::Create(options.line_search_type, 1981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_options, 19979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez &summary->message)); 2001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (line_search.get() == NULL) { 20179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->termination_type = FAILURE; 20279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG_IF(ERROR, is_not_silent) << "Terminating: " << summary->message; 2031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return; 2041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 2051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearch::Summary line_search_summary; 2071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int num_line_search_direction_restarts = 0; 2081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling while (true) { 21079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (!RunCallbacks(options, iteration_summary, summary)) { 21179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez break; 2121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 2131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_start_time = WallTimeInSeconds(); 2151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (iteration_summary.iteration >= options.max_num_iterations) { 21679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->message = "Maximum number of iterations reached."; 2171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->termination_type = NO_CONVERGENCE; 21879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message; 2191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling break; 2201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 2211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double total_solver_time = iteration_start_time - start_time + 2231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->preprocessor_time_in_seconds; 2241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (total_solver_time >= options.max_solver_time_in_seconds) { 22579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->message = "Maximum solver time reached."; 2261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->termination_type = NO_CONVERGENCE; 22779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message; 2281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling break; 2291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 2301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary = IterationSummary(); 2321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.iteration = summary->iterations.back().iteration + 1; 2331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.step_is_valid = false; 2341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.step_is_successful = false; 2351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bool line_search_status = true; 2371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (iteration_summary.iteration == 1) { 2381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current_state.search_direction = -current_state.gradient; 2391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } else { 2401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_status = line_search_direction->NextDirection( 2411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling previous_state, 2421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current_state, 2431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ¤t_state.search_direction); 2441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 2451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2461d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (!line_search_status && 2471d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling num_line_search_direction_restarts >= 2481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.max_num_line_search_direction_restarts) { 2491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Line search direction failed to generate a new direction, and we 2501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // have already reached our specified maximum number of restarts, 2511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // terminate optimization. 25279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->message = 2531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling StringPrintf("Line search direction failure: specified " 2541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "max_num_line_search_direction_restarts: %d reached.", 2551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.max_num_line_search_direction_restarts); 25679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->termination_type = FAILURE; 25779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG_IF(WARNING, is_not_silent) << "Terminating: " << summary->message; 2581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling break; 2591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } else if (!line_search_status) { 2601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Restart line search direction with gradient descent on first iteration 2611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // as we have not yet reached our maximum number of restarts. 2621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling CHECK_LT(num_line_search_direction_restarts, 2631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options.max_num_line_search_direction_restarts); 2641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ++num_line_search_direction_restarts; 26679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG_IF(WARNING, is_not_silent) 2671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << "Line search direction algorithm: " 26879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << LineSearchDirectionTypeToString( 26979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez options.line_search_direction_type) 27079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << ", failed to produce a valid new direction at " 27179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << "iteration: " << iteration_summary.iteration 27279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << ". Restarting, number of restarts: " 27379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << num_line_search_direction_restarts << " / " 27479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << options.max_num_line_search_direction_restarts 27579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << " [max]."; 2761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_direction.reset( 2771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchDirection::Create(line_search_direction_options)); 2781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current_state.search_direction = -current_state.gradient; 2791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 2801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_function.Init(x, current_state.search_direction); 2821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current_state.directional_derivative = 2831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current_state.gradient.dot(current_state.search_direction); 2841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // TODO(sameeragarwal): Refactor this into its own object and add 2861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // explanations for the various choices. 2871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Note that we use !line_search_status to ensure that we treat cases when 2891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // we restarted the line search direction equivalently to the first 2901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // iteration. 2911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double initial_step_size = 2921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling (iteration_summary.iteration == 1 || !line_search_status) 2931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ? min(1.0, 1.0 / current_state.gradient_max_norm) 2941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling : min(1.0, 2.0 * (current_state.cost - previous_state.cost) / 2951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current_state.directional_derivative); 2961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // By definition, we should only ever go forwards along the specified search 2971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // direction in a line search, most likely cause for this being violated 2981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // would be a numerical failure in the line search direction calculation. 2991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (initial_step_size < 0.0) { 30079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->message = 3011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling StringPrintf("Numerical failure in line search, initial_step_size is " 3021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "negative: %.5e, directional_derivative: %.5e, " 3031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "(current_cost - previous_cost): %.5e", 3041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling initial_step_size, current_state.directional_derivative, 3051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling (current_state.cost - previous_state.cost)); 30679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->termination_type = FAILURE; 30779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG_IF(WARNING, is_not_silent) << "Terminating: " << summary->message; 3081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling break; 3091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 3101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 3111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search->Search(initial_step_size, 3121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current_state.cost, 3131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current_state.directional_derivative, 3141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling &line_search_summary); 31579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (!line_search_summary.success) { 31679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->message = 31779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez StringPrintf("Numerical failure in line search, failed to find " 31879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "a valid step size, (did not run out of iterations) " 31979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "using initial_step_size: %.5e, initial_cost: %.5e, " 32079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "initial_gradient: %.5e.", 32179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez initial_step_size, current_state.cost, 32279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez current_state.directional_derivative); 32379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG_IF(WARNING, is_not_silent) << "Terminating: " << summary->message; 32479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->termination_type = FAILURE; 32579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez break; 32679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez } 3271d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 3281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current_state.step_size = line_search_summary.optimal_step_size; 3291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling delta = current_state.step_size * current_state.search_direction; 3301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 3311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling previous_state = current_state; 3321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.step_solver_time_in_seconds = 3331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling WallTimeInSeconds() - iteration_start_time; 3341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 33579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (!evaluator->Plus(x.data(), delta.data(), x_plus_delta.data())) { 33679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->termination_type = FAILURE; 33779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->message = 33879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "x_plus_delta = Plus(x, delta) failed. This should not happen " 33979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "as the step was valid when it was selected by the line search."; 34079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG_IF(WARNING, is_not_silent) << "Terminating: " << summary->message; 34179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez break; 34279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez } else if (!Evaluate(evaluator, 34379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez x_plus_delta, 34479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez ¤t_state, 34579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez &summary->message)) { 34679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->termination_type = FAILURE; 34779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->message = 34879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "Step failed to evaluate. This should not happen as the step was " 34979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "valid when it was selected by the line search. More details: " + 35079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->message; 35179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG_IF(WARNING, is_not_silent) << "Terminating: " << summary->message; 35279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez break; 3531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } else { 3541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling x = x_plus_delta; 3551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 3561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 3571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.gradient_max_norm = current_state.gradient_max_norm; 35879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez iteration_summary.gradient_norm = sqrt(current_state.gradient_squared_norm); 3591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.cost_change = previous_state.cost - current_state.cost; 3601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.cost = current_state.cost + summary->fixed_cost; 3611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.step_norm = delta.norm(); 3621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.step_is_valid = true; 3631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.step_is_successful = true; 3641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.step_norm = delta.norm(); 3651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.step_size = current_state.step_size; 3661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.line_search_function_evaluations = 3671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_summary.num_function_evaluations; 3681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.line_search_gradient_evaluations = 3691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_summary.num_gradient_evaluations; 3701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.line_search_iterations = 3711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search_summary.num_iterations; 3721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.iteration_time_in_seconds = 3731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling WallTimeInSeconds() - iteration_start_time; 3741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling iteration_summary.cumulative_time_in_seconds = 3751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling WallTimeInSeconds() - start_time 3761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling + summary->preprocessor_time_in_seconds; 3771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 3781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->iterations.push_back(iteration_summary); 3791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ++summary->num_successful_steps; 38079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 38179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (iteration_summary.gradient_max_norm <= options.gradient_tolerance) { 38279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->message = StringPrintf("Gradient tolerance reached. " 38379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "Gradient max norm: %e <= %e", 38479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez iteration_summary.gradient_max_norm, 38579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez options.gradient_tolerance); 38679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->termination_type = CONVERGENCE; 38779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message; 38879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez break; 38979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez } 39079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 39179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez const double absolute_function_tolerance = 39279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez options.function_tolerance * previous_state.cost; 39379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (fabs(iteration_summary.cost_change) < absolute_function_tolerance) { 39479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->message = 39579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez StringPrintf("Function tolerance reached. " 39679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "|cost_change|/cost: %e <= %e", 39779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez fabs(iteration_summary.cost_change) / 39879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez previous_state.cost, 39979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez options.function_tolerance); 40079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->termination_type = CONVERGENCE; 40179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message; 40279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez break; 40379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez } 4041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 4051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} 4061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} // namespace internal 4081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} // namespace ceres 409