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 3179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez#include <iomanip> 3279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez#include <iostream> // NOLINT 3379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/line_search.h" 351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/fpclassify.h" 371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/evaluator.h" 381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/internal/eigen.h" 391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/polynomial.h" 401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/stringprintf.h" 411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "glog/logging.h" 421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingnamespace ceres { 441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingnamespace internal { 451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingnamespace { 4679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// Precision used for floating point values in error message output. 4779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandezconst int kErrorMessageNumericPrecision = 8; 481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha HaeberlingFunctionSample ValueSample(const double x, const double value) { 501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FunctionSample sample; 511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling sample.x = x; 521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling sample.value = value; 531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling sample.value_is_valid = true; 541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return sample; 551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling}; 561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha HaeberlingFunctionSample ValueAndGradientSample(const double x, 581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double value, 591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double gradient) { 601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FunctionSample sample; 611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling sample.x = x; 621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling sample.value = value; 631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling sample.gradient = gradient; 641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling sample.value_is_valid = true; 651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling sample.gradient_is_valid = true; 661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return sample; 671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling}; 681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} // namespace 701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 7279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandezstd::ostream& operator<<(std::ostream &os, const FunctionSample& sample); 7379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// Convenience stream operator for pushing FunctionSamples into log messages. 7579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandezstd::ostream& operator<<(std::ostream &os, const FunctionSample& sample) { 7679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez os << sample.ToDebugString(); 771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return os; 781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} 791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha HaeberlingLineSearch::LineSearch(const LineSearch::Options& options) 811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling : options_(options) {} 821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha HaeberlingLineSearch* LineSearch::Create(const LineSearchType line_search_type, 841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const LineSearch::Options& options, 851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling string* error) { 861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearch* line_search = NULL; 871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling switch (line_search_type) { 881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling case ceres::ARMIJO: 891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search = new ArmijoLineSearch(options); 901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling break; 911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling case ceres::WOLFE: 921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling line_search = new WolfeLineSearch(options); 931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling break; 941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling default: 951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *error = string("Invalid line search algorithm type: ") + 961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchTypeToString(line_search_type) + 971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling string(", unable to create line search."); 981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return NULL; 991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 1001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return line_search; 1011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} 1021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha HaeberlingLineSearchFunction::LineSearchFunction(Evaluator* evaluator) 1041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling : evaluator_(evaluator), 1051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling position_(evaluator->NumParameters()), 1061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling direction_(evaluator->NumEffectiveParameters()), 1071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling evaluation_point_(evaluator->NumParameters()), 1081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling scaled_direction_(evaluator->NumEffectiveParameters()), 1091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling gradient_(evaluator->NumEffectiveParameters()) { 1101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} 1111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingvoid LineSearchFunction::Init(const Vector& position, 1131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const Vector& direction) { 1141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling position_ = position; 1151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling direction_ = direction; 1161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} 1171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 118399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettingerbool LineSearchFunction::Evaluate(double x, double* f, double* g) { 1191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling scaled_direction_ = x * direction_; 1201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (!evaluator_->Plus(position_.data(), 1211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling scaled_direction_.data(), 1221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling evaluation_point_.data())) { 1231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return false; 1241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 1251d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (g == NULL) { 1271d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return (evaluator_->Evaluate(evaluation_point_.data(), 1281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling f, NULL, NULL, NULL) && 1291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling IsFinite(*f)); 1301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 1311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (!evaluator_->Evaluate(evaluation_point_.data(), 1331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling f, 1341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling NULL, 1351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling gradient_.data(), NULL)) { 1361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return false; 1371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 1381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *g = direction_.dot(gradient_); 1401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return IsFinite(*f) && IsFinite(*g); 1411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} 1421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingdouble LineSearchFunction::DirectionInfinityNorm() const { 1441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return direction_.lpNorm<Eigen::Infinity>(); 1451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} 1461d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1471d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// Returns step_size \in [min_step_size, max_step_size] which minimizes the 1481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// polynomial of degree defined by interpolation_type which interpolates all 1491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// of the provided samples with valid values. 1501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingdouble LineSearch::InterpolatingPolynomialMinimizingStepSize( 1511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const LineSearchInterpolationType& interpolation_type, 1521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const FunctionSample& lowerbound, 1531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const FunctionSample& previous, 1541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const FunctionSample& current, 1551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double min_step_size, 1561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double max_step_size) const { 1571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (!current.value_is_valid || 1581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling (interpolation_type == BISECTION && 1591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling max_step_size <= current.x)) { 1601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Either: sample is invalid; or we are using BISECTION and contracting 1611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // the step size. 1621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return min(max(current.x * 0.5, min_step_size), max_step_size); 1631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } else if (interpolation_type == BISECTION) { 1641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling CHECK_GT(max_step_size, current.x); 1651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // We are expanding the search (during a Wolfe bracketing phase) using 1661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // BISECTION interpolation. Using BISECTION when trying to expand is 1671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // strictly speaking an oxymoron, but we define this to mean always taking 1681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // the maximum step size so that the Armijo & Wolfe implementations are 1691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // agnostic to the interpolation type. 1701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return max_step_size; 1711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 1721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Only check if lower-bound is valid here, where it is required 1731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // to avoid replicating current.value_is_valid == false 1741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // behaviour in WolfeLineSearch. 1751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling CHECK(lowerbound.value_is_valid) 17679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << std::scientific << std::setprecision(kErrorMessageNumericPrecision) 1771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << "Ceres bug: lower-bound sample for interpolation is invalid, " 1781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << "please contact the developers!, interpolation_type: " 1791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << LineSearchInterpolationTypeToString(interpolation_type) 1801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << ", lowerbound: " << lowerbound << ", previous: " << previous 1811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << ", current: " << current; 1821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Select step size by interpolating the function and gradient values 1841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // and minimizing the corresponding polynomial. 1851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling vector<FunctionSample> samples; 1861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling samples.push_back(lowerbound); 1871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (interpolation_type == QUADRATIC) { 1891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Two point interpolation using function values and the 1901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // gradient at the lower bound. 1911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling samples.push_back(ValueSample(current.x, current.value)); 1921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (previous.value_is_valid) { 1941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Three point interpolation, using function values and the 1951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // gradient at the lower bound. 1961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling samples.push_back(ValueSample(previous.x, previous.value)); 1971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 1981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } else if (interpolation_type == CUBIC) { 1991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Two point interpolation using the function values and the gradients. 2001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling samples.push_back(current); 2011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (previous.value_is_valid) { 2031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Three point interpolation using the function values and 2041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // the gradients. 2051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling samples.push_back(previous); 2061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 2071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } else { 2081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LOG(FATAL) << "Ceres bug: No handler for interpolation_type: " 2091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << LineSearchInterpolationTypeToString(interpolation_type) 2101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << ", please contact the developers!"; 2111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 2121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double step_size = 0.0, unused_min_value = 0.0; 2141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling MinimizeInterpolatingPolynomial(samples, min_step_size, max_step_size, 2151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling &step_size, &unused_min_value); 2161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return step_size; 2171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} 2181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha HaeberlingArmijoLineSearch::ArmijoLineSearch(const LineSearch::Options& options) 2201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling : LineSearch(options) {} 2211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingvoid ArmijoLineSearch::Search(const double step_size_estimate, 2231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double initial_cost, 2241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double initial_gradient, 2251d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Summary* summary) { 2261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *CHECK_NOTNULL(summary) = LineSearch::Summary(); 2271d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling CHECK_GE(step_size_estimate, 0.0); 2281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling CHECK_GT(options().sufficient_decrease, 0.0); 2291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling CHECK_LT(options().sufficient_decrease, 1.0); 2301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling CHECK_GT(options().max_num_iterations, 0); 2311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Function* function = options().function; 2321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Note initial_cost & initial_gradient are evaluated at step_size = 0, 2341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // not step_size_estimate, which is our starting guess. 2351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const FunctionSample initial_position = 2361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ValueAndGradientSample(0.0, initial_cost, initial_gradient); 2371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FunctionSample previous = ValueAndGradientSample(0.0, 0.0, 0.0); 2391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling previous.value_is_valid = false; 2401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FunctionSample current = ValueAndGradientSample(step_size_estimate, 0.0, 0.0); 2421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current.value_is_valid = false; 2431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 24479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // As the Armijo line search algorithm always uses the initial point, for 24579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // which both the function value and derivative are known, when fitting a 24679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // minimizing polynomial, we can fit up to a quadratic without requiring the 24779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // gradient at the current query point. 24879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez const bool interpolation_uses_gradient_at_current_sample = 2491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options().interpolation_type == CUBIC; 2501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double descent_direction_max_norm = 2511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling static_cast<const LineSearchFunction*>(function)->DirectionInfinityNorm(); 2521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ++summary->num_function_evaluations; 25479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (interpolation_uses_gradient_at_current_sample) { 25579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez ++summary->num_gradient_evaluations; 25679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez } 2571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current.value_is_valid = 2581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling function->Evaluate(current.x, 2591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ¤t.value, 26079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez interpolation_uses_gradient_at_current_sample 2611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ? ¤t.gradient : NULL); 2621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current.gradient_is_valid = 26379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez interpolation_uses_gradient_at_current_sample && current.value_is_valid; 2641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling while (!current.value_is_valid || 2651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current.value > (initial_cost 2661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling + options().sufficient_decrease 2671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling * initial_gradient 2681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling * current.x)) { 2691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // If current.value_is_valid is false, we treat it as if the cost at that 2701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // point is not large enough to satisfy the sufficient decrease condition. 2711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ++summary->num_iterations; 2721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (summary->num_iterations >= options().max_num_iterations) { 2731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->error = 2741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling StringPrintf("Line search failed: Armijo failed to find a point " 2751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "satisfying the sufficient decrease condition within " 2761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "specified max_num_iterations: %d.", 2771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options().max_num_iterations); 27879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG_IF(WARNING, !options().is_silent) << summary->error; 2791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return; 2801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 2811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double step_size = 2831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling this->InterpolatingPolynomialMinimizingStepSize( 2841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options().interpolation_type, 2851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling initial_position, 2861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling previous, 2871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current, 2881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling (options().max_step_contraction * current.x), 2891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling (options().min_step_contraction * current.x)); 2901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (step_size * descent_direction_max_norm < options().min_step_size) { 2921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->error = 2931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling StringPrintf("Line search failed: step_size too small: %.5e " 2941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "with descent_direction_max_norm: %.5e.", step_size, 2951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling descent_direction_max_norm); 29679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG_IF(WARNING, !options().is_silent) << summary->error; 2971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return; 2981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 2991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 3001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling previous = current; 3011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current.x = step_size; 3021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 3031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ++summary->num_function_evaluations; 30479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (interpolation_uses_gradient_at_current_sample) { 30579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez ++summary->num_gradient_evaluations; 30679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez } 3071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current.value_is_valid = 3081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling function->Evaluate(current.x, 3091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ¤t.value, 31079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez interpolation_uses_gradient_at_current_sample 3111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ? ¤t.gradient : NULL); 3121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current.gradient_is_valid = 31379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez interpolation_uses_gradient_at_current_sample && current.value_is_valid; 3141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 3151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 3161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->optimal_step_size = current.x; 3171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->success = true; 3181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} 3191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 3201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha HaeberlingWolfeLineSearch::WolfeLineSearch(const LineSearch::Options& options) 3211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling : LineSearch(options) {} 3221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 3231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingvoid WolfeLineSearch::Search(const double step_size_estimate, 3241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double initial_cost, 3251d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double initial_gradient, 3261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Summary* summary) { 3271d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *CHECK_NOTNULL(summary) = LineSearch::Summary(); 3281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // All parameters should have been validated by the Solver, but as 3291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // invalid values would produce crazy nonsense, hard check them here. 3301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling CHECK_GE(step_size_estimate, 0.0); 3311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling CHECK_GT(options().sufficient_decrease, 0.0); 3321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling CHECK_GT(options().sufficient_curvature_decrease, 3331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options().sufficient_decrease); 3341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling CHECK_LT(options().sufficient_curvature_decrease, 1.0); 3351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling CHECK_GT(options().max_step_expansion, 1.0); 3361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 3371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Note initial_cost & initial_gradient are evaluated at step_size = 0, 3381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // not step_size_estimate, which is our starting guess. 3391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const FunctionSample initial_position = 3401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ValueAndGradientSample(0.0, initial_cost, initial_gradient); 3411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 3421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bool do_zoom_search = false; 3431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Important: The high/low in bracket_high & bracket_low refer to their 3441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // _function_ values, not their step sizes i.e. it is _not_ required that 3451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // bracket_low.x < bracket_high.x. 3461d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FunctionSample solution, bracket_low, bracket_high; 3471d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 3481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Wolfe bracketing phase: Increases step_size until either it finds a point 3491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // that satisfies the (strong) Wolfe conditions, or an interval that brackets 3501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // step sizes which satisfy the conditions. From Nocedal & Wright [1] p61 the 3511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // interval: (step_size_{k-1}, step_size_{k}) contains step lengths satisfying 3521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // the strong Wolfe conditions if one of the following conditions are met: 3531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 3541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1. step_size_{k} violates the sufficient decrease (Armijo) condition. 3551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2. f(step_size_{k}) >= f(step_size_{k-1}). 3561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 3. f'(step_size_{k}) >= 0. 3571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 3581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Caveat: If f(step_size_{k}) is invalid, then step_size is reduced, ignoring 3591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // this special case, step_size monotonically increases during bracketing. 3601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (!this->BracketingPhase(initial_position, 3611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling step_size_estimate, 3621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling &bracket_low, 3631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling &bracket_high, 3641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling &do_zoom_search, 36579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary)) { 36679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // Failed to find either a valid point, a valid bracket satisfying the Wolfe 36779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // conditions, or even a step size > minimum tolerance satisfying the Armijo 36879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // condition. 3691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return; 3701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 37179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 3721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (!do_zoom_search) { 3731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Either: Bracketing phase already found a point satisfying the strong 3741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Wolfe conditions, thus no Zoom required. 3751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 3761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Or: Bracketing failed to find a valid bracket or a point satisfying the 37779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // strong Wolfe conditions within max_num_iterations, or whilst searching 37879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // shrank the bracket width until it was below our minimum tolerance. 37979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // As these are 'artificial' constraints, and we would otherwise fail to 38079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // produce a valid point when ArmijoLineSearch would succeed, we return the 38179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // point with the lowest cost found thus far which satsifies the Armijo 38279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // condition (but not the Wolfe conditions). 3831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->optimal_step_size = bracket_low.x; 3841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->success = true; 3851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return; 3861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 3871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 38879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez VLOG(3) << std::scientific << std::setprecision(kErrorMessageNumericPrecision) 38979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << "Starting line search zoom phase with bracket_low: " 39079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << bracket_low << ", bracket_high: " << bracket_high 39179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << ", bracket width: " << fabs(bracket_low.x - bracket_high.x) 39279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << ", bracket abs delta cost: " 39379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << fabs(bracket_low.value - bracket_high.value); 39479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 3951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Wolfe Zoom phase: Called when the Bracketing phase finds an interval of 3961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // non-zero, finite width that should bracket step sizes which satisfy the 3971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // (strong) Wolfe conditions (before finding a step size that satisfies the 3981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // conditions). Zoom successively decreases the size of the interval until a 3991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // step size which satisfies the Wolfe conditions is found. The interval is 4001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // defined by bracket_low & bracket_high, which satisfy: 4011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 4021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1. The interval bounded by step sizes: bracket_low.x & bracket_high.x 4031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // contains step sizes that satsify the strong Wolfe conditions. 4041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2. bracket_low.x is of all the step sizes evaluated *which satisifed the 4051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Armijo sufficient decrease condition*, the one which generated the 4061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // smallest function value, i.e. bracket_low.value < 4071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // f(all other steps satisfying Armijo). 4081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // - Note that this does _not_ (necessarily) mean that initially 4091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // bracket_low.value < bracket_high.value (although this is typical) 4101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // e.g. when bracket_low = initial_position, and bracket_high is the 4111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // first sample, and which does not satisfy the Armijo condition, 4121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // but still has bracket_high.value < initial_position.value. 4131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 3. bracket_high is chosen after bracket_low, s.t. 4141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // bracket_low.gradient * (bracket_high.x - bracket_low.x) < 0. 4151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (!this->ZoomPhase(initial_position, 4161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bracket_low, 4171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bracket_high, 4181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling &solution, 4191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary) && !solution.value_is_valid) { 4201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Failed to find a valid point (given the specified decrease parameters) 4211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // within the specified bracket. 4221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return; 4231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 4241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Ensure that if we ran out of iterations whilst zooming the bracket, or 4251d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // shrank the bracket width to < tolerance and failed to find a point which 4261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // satisfies the strong Wolfe curvature condition, that we return the point 4271d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // amongst those found thus far, which minimizes f() and satisfies the Armijo 4281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // condition. 4291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling solution = 4301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling solution.value_is_valid && solution.value <= bracket_low.value 4311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ? solution : bracket_low; 4321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->optimal_step_size = solution.x; 4341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->success = true; 4351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} 4361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 43779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// Returns true if either: 43879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// 43979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// A termination condition satisfying the (strong) Wolfe bracketing conditions 44079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// is found: 44179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// 44279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// - A valid point, defined as a bracket of zero width [zoom not required]. 44379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// - A valid bracket (of width > tolerance), [zoom required]. 44479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// 44579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// Or, searching was stopped due to an 'artificial' constraint, i.e. not 44679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// a condition imposed / required by the underlying algorithm, but instead an 44779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// engineering / implementation consideration. But a step which exceeds the 44879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// minimum step size, and satsifies the Armijo condition was still found, 44979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// and should thus be used [zoom not required]. 45079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// 45179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// Returns false if no step size > minimum step size was found which 45279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// satisfies at least the Armijo condition. 4531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingbool WolfeLineSearch::BracketingPhase( 4541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const FunctionSample& initial_position, 4551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double step_size_estimate, 4561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FunctionSample* bracket_low, 4571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FunctionSample* bracket_high, 4581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bool* do_zoom_search, 4591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Summary* summary) { 4601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Function* function = options().function; 4611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FunctionSample previous = initial_position; 4631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FunctionSample current = ValueAndGradientSample(step_size_estimate, 0.0, 0.0); 4641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current.value_is_valid = false; 4651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double descent_direction_max_norm = 4671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling static_cast<const LineSearchFunction*>(function)->DirectionInfinityNorm(); 4681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *do_zoom_search = false; 4701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *bracket_low = initial_position; 4711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 47279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // As we require the gradient to evaluate the Wolfe condition, we always 47379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // calculate it together with the value, irrespective of the interpolation 47479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // type. As opposed to only calculating the gradient after the Armijo 47579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // condition is satisifed, as the computational saving from this approach 47679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // would be slight (perhaps even negative due to the extra call). Also, 47779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // always calculating the value & gradient together protects against us 47879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // reporting invalid solutions if the cost function returns slightly different 47979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // function values when evaluated with / without gradients (due to numerical 48079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // issues). 4811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ++summary->num_function_evaluations; 48279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez ++summary->num_gradient_evaluations; 4831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current.value_is_valid = 4841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling function->Evaluate(current.x, 4851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ¤t.value, 48679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez ¤t.gradient); 48779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez current.gradient_is_valid = current.value_is_valid; 4881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling while (true) { 4901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ++summary->num_iterations; 4911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 4921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (current.value_is_valid && 4931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling (current.value > (initial_position.value 4941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling + options().sufficient_decrease 4951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling * initial_position.gradient 4961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling * current.x) || 4971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling (previous.value_is_valid && current.value > previous.value))) { 4981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Bracket found: current step size violates Armijo sufficient decrease 4991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // condition, or has stepped past an inflection point of f() relative to 5001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // previous step size. 5011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *do_zoom_search = true; 5021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *bracket_low = previous; 5031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *bracket_high = current; 50479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez VLOG(3) << std::scientific 50579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << std::setprecision(kErrorMessageNumericPrecision) 50679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << "Bracket found: current step (" << current.x 50779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << ") violates Armijo sufficient condition, or has passed an " 50879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << "inflection point of f() based on value."; 5091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling break; 5101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 5111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (current.value_is_valid && 5131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling fabs(current.gradient) <= 5141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling -options().sufficient_curvature_decrease * initial_position.gradient) { 5151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Current step size satisfies the strong Wolfe conditions, and is thus a 5161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // valid termination point, therefore a Zoom not required. 5171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *bracket_low = current; 5181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *bracket_high = current; 51979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez VLOG(3) << std::scientific 52079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << std::setprecision(kErrorMessageNumericPrecision) 52179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << "Bracketing phase found step size: " << current.x 52279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << ", satisfying strong Wolfe conditions, initial_position: " 52379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << initial_position << ", current: " << current; 5241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling break; 5251d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } else if (current.value_is_valid && current.gradient >= 0) { 5271d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Bracket found: current step size has stepped past an inflection point 5281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // of f(), but Armijo sufficient decrease is still satisfied and 5291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // f(current) is our best minimum thus far. Remember step size 5301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // monotonically increases, thus previous_step_size < current_step_size 5311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // even though f(previous) > f(current). 5321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *do_zoom_search = true; 5331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Note inverse ordering from first bracket case. 5341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *bracket_low = current; 5351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *bracket_high = previous; 53679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez VLOG(3) << "Bracket found: current step (" << current.x 53779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << ") satisfies Armijo, but has gradient >= 0, thus have passed " 53879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << "an inflection point of f()."; 53979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez break; 54079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 54179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez } else if (current.value_is_valid && 54279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez fabs(current.x - previous.x) * descent_direction_max_norm 54379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez < options().min_step_size) { 54479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // We have shrunk the search bracket to a width less than our tolerance, 54579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // and still not found either a point satisfying the strong Wolfe 54679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // conditions, or a valid bracket containing such a point. Stop searching 54779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // and set bracket_low to the size size amongst all those tested which 54879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // minimizes f() and satisfies the Armijo condition. 54979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG_IF(WARNING, !options().is_silent) 55079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << "Line search failed: Wolfe bracketing phase shrank " 55179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << "bracket width: " << fabs(current.x - previous.x) 55279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << ", to < tolerance: " << options().min_step_size 55379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << ", with descent_direction_max_norm: " 55479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << descent_direction_max_norm << ", and failed to find " 55579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << "a point satisfying the strong Wolfe conditions or a " 55679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << "bracketing containing such a point. Accepting " 55779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << "point found satisfying Armijo condition only, to " 55879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << "allow continuation."; 55979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez *bracket_low = current; 5601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling break; 5611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } else if (summary->num_iterations >= options().max_num_iterations) { 5631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Check num iterations bound here so that we always evaluate the 5641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // max_num_iterations-th iteration against all conditions, and 5651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // then perform no additional (unused) evaluations. 5661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->error = 5671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling StringPrintf("Line search failed: Wolfe bracketing phase failed to " 5681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "find a point satisfying strong Wolfe conditions, or a " 5691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "bracket containing such a point within specified " 5701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "max_num_iterations: %d", options().max_num_iterations); 57179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG_IF(WARNING, !options().is_silent) << summary->error; 5721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Ensure that bracket_low is always set to the step size amongst all 5731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // those tested which minimizes f() and satisfies the Armijo condition 5741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // when we terminate due to the 'artificial' max_num_iterations condition. 5751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *bracket_low = 5761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current.value_is_valid && current.value < bracket_low->value 5771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ? current : *bracket_low; 57879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez break; 5791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 5801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Either: f(current) is invalid; or, f(current) is valid, but does not 5811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // satisfy the strong Wolfe conditions itself, or the conditions for 5821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // being a boundary of a bracket. 5831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // If f(current) is valid, (but meets no criteria) expand the search by 5851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // increasing the step size. 5861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double max_step_size = 5871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current.value_is_valid 5881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ? (current.x * options().max_step_expansion) : current.x; 5891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 5901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // We are performing 2-point interpolation only here, but the API of 5911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // InterpolatingPolynomialMinimizingStepSize() allows for up to 5921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 3-point interpolation, so pad call with a sample with an invalid 5931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // value that will therefore be ignored. 5941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const FunctionSample unused_previous; 5951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling DCHECK(!unused_previous.value_is_valid); 5961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Contracts step size if f(current) is not valid. 5971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double step_size = 5981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling this->InterpolatingPolynomialMinimizingStepSize( 5991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options().interpolation_type, 6001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling previous, 6011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling unused_previous, 6021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current, 6031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling previous.x, 6041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling max_step_size); 6051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (step_size * descent_direction_max_norm < options().min_step_size) { 6061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->error = 6071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling StringPrintf("Line search failed: step_size too small: %.5e " 6081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "with descent_direction_max_norm: %.5e", step_size, 6091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling descent_direction_max_norm); 61079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG_IF(WARNING, !options().is_silent) << summary->error; 6111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return false; 6121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 6131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 6141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling previous = current.value_is_valid ? current : previous; 6151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current.x = step_size; 6161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 6171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ++summary->num_function_evaluations; 61879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez ++summary->num_gradient_evaluations; 6191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling current.value_is_valid = 6201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling function->Evaluate(current.x, 6211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ¤t.value, 62279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez ¤t.gradient); 62379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez current.gradient_is_valid = current.value_is_valid; 62479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez } 62579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 62679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // Ensure that even if a valid bracket was found, we will only mark a zoom 62779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // as required if the bracket's width is greater than our minimum tolerance. 62879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (*do_zoom_search && 62979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez fabs(bracket_high->x - bracket_low->x) * descent_direction_max_norm 63079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez < options().min_step_size) { 63179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez *do_zoom_search = false; 6321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 63379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 6341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return true; 6351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} 6361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 6371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// Returns true iff solution satisfies the strong Wolfe conditions. Otherwise, 6381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// on return false, if we stopped searching due to the 'artificial' condition of 6391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// reaching max_num_iterations, solution is the step size amongst all those 6401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// tested, which satisfied the Armijo decrease condition and minimized f(). 6411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingbool WolfeLineSearch::ZoomPhase(const FunctionSample& initial_position, 6421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FunctionSample bracket_low, 6431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FunctionSample bracket_high, 6441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FunctionSample* solution, 6451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Summary* summary) { 6461d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Function* function = options().function; 6471d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 6481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling CHECK(bracket_low.value_is_valid && bracket_low.gradient_is_valid) 64979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << std::scientific << std::setprecision(kErrorMessageNumericPrecision) 6501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << "Ceres bug: f_low input to Wolfe Zoom invalid, please contact " 6511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << "the developers!, initial_position: " << initial_position 6521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << ", bracket_low: " << bracket_low 6531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << ", bracket_high: "<< bracket_high; 6541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // We do not require bracket_high.gradient_is_valid as the gradient condition 6551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // for a valid bracket is only dependent upon bracket_low.gradient, and 6561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // in order to minimize jacobian evaluations, bracket_high.gradient may 6571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // not have been calculated (if bracket_high.value does not satisfy the 6581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Armijo sufficient decrease condition and interpolation method does not 6591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // require it). 66079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // 66179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // We also do not require that: bracket_low.value < bracket_high.value, 66279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // although this is typical. This is to deal with the case when 66379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // bracket_low = initial_position, bracket_high is the first sample, 66479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // and bracket_high does not satisfy the Armijo condition, but still has 66579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // bracket_high.value < initial_position.value. 6661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling CHECK(bracket_high.value_is_valid) 66779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << std::scientific << std::setprecision(kErrorMessageNumericPrecision) 6681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << "Ceres bug: f_high input to Wolfe Zoom invalid, please " 6691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << "contact the developers!, initial_position: " << initial_position 6701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << ", bracket_low: " << bracket_low 6711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling << ", bracket_high: "<< bracket_high; 67279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 67379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez if (bracket_low.gradient * (bracket_high.x - bracket_low.x) >= 0) { 67479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // The third condition for a valid initial bracket: 67579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // 67679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // 3. bracket_high is chosen after bracket_low, s.t. 67779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // bracket_low.gradient * (bracket_high.x - bracket_low.x) < 0. 67879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // 67979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // is not satisfied. As this can happen when the users' cost function 68079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // returns inconsistent gradient values relative to the function values, 68179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // we do not CHECK_LT(), but we do stop processing and return an invalid 68279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // value. 68379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez summary->error = 68479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez StringPrintf("Line search failed: Wolfe zoom phase passed a bracket " 68579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "which does not satisfy: bracket_low.gradient * " 68679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "(bracket_high.x - bracket_low.x) < 0 [%.8e !< 0] " 68779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "with initial_position: %s, bracket_low: %s, bracket_high:" 68879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez " %s, the most likely cause of which is the cost function " 68979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez "returning inconsistent gradient & function values.", 69079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez bracket_low.gradient * (bracket_high.x - bracket_low.x), 69179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez initial_position.ToDebugString().c_str(), 69279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez bracket_low.ToDebugString().c_str(), 69379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez bracket_high.ToDebugString().c_str()); 69479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG_IF(WARNING, !options().is_silent) << summary->error; 69579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez solution->value_is_valid = false; 69679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez return false; 69779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez } 6981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 6991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const int num_bracketing_iterations = summary->num_iterations; 7001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double descent_direction_max_norm = 7011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling static_cast<const LineSearchFunction*>(function)->DirectionInfinityNorm(); 7021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling while (true) { 7041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Set solution to bracket_low, as it is our best step size (smallest f()) 7051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // found thus far and satisfies the Armijo condition, even though it does 7061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // not satisfy the Wolfe condition. 7071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling *solution = bracket_low; 7081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (summary->num_iterations >= options().max_num_iterations) { 7091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->error = 7101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling StringPrintf("Line search failed: Wolfe zoom phase failed to " 7111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "find a point satisfying strong Wolfe conditions " 7121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "within specified max_num_iterations: %d, " 7131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "(num iterations taken for bracketing: %d).", 7141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options().max_num_iterations, num_bracketing_iterations); 71579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG_IF(WARNING, !options().is_silent) << summary->error; 7161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return false; 7171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 7181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (fabs(bracket_high.x - bracket_low.x) * descent_direction_max_norm 7191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling < options().min_step_size) { 7201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Bracket width has been reduced below tolerance, and no point satisfying 7211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // the strong Wolfe conditions has been found. 7221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->error = 7231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling StringPrintf("Line search failed: Wolfe zoom bracket width: %.5e " 7241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "too small with descent_direction_max_norm: %.5e.", 7251d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling fabs(bracket_high.x - bracket_low.x), 7261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling descent_direction_max_norm); 72779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG_IF(WARNING, !options().is_silent) << summary->error; 7281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return false; 7291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 7301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ++summary->num_iterations; 7321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Polynomial interpolation requires inputs ordered according to step size, 7331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // not f(step size). 7341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const FunctionSample& lower_bound_step = 7351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bracket_low.x < bracket_high.x ? bracket_low : bracket_high; 7361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const FunctionSample& upper_bound_step = 7371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bracket_low.x < bracket_high.x ? bracket_high : bracket_low; 7381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // We are performing 2-point interpolation only here, but the API of 7391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // InterpolatingPolynomialMinimizingStepSize() allows for up to 7401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 3-point interpolation, so pad call with a sample with an invalid 7411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // value that will therefore be ignored. 7421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const FunctionSample unused_previous; 7431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling DCHECK(!unused_previous.value_is_valid); 7441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling solution->x = 7451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling this->InterpolatingPolynomialMinimizingStepSize( 7461d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling options().interpolation_type, 7471d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling lower_bound_step, 7481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling unused_previous, 7491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling upper_bound_step, 7501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling lower_bound_step.x, 7511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling upper_bound_step.x); 7521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // No check on magnitude of step size being too small here as it is 7531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // lower-bounded by the initial bracket start point, which was valid. 75479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // 75579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // As we require the gradient to evaluate the Wolfe condition, we always 75679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // calculate it together with the value, irrespective of the interpolation 75779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // type. As opposed to only calculating the gradient after the Armijo 75879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // condition is satisifed, as the computational saving from this approach 75979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // would be slight (perhaps even negative due to the extra call). Also, 76079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // always calculating the value & gradient together protects against us 76179397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // reporting invalid solutions if the cost function returns slightly 76279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // different function values when evaluated with / without gradients (due 76379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez // to numerical issues). 7641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ++summary->num_function_evaluations; 76579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez ++summary->num_gradient_evaluations; 7661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling solution->value_is_valid = 7671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling function->Evaluate(solution->x, 7681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling &solution->value, 76979397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez &solution->gradient); 77079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez solution->gradient_is_valid = solution->value_is_valid; 7711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (!solution->value_is_valid) { 7721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling summary->error = 7731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling StringPrintf("Line search failed: Wolfe Zoom phase found " 7741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "step_size: %.5e, for which function is invalid, " 7751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "between low_step: %.5e and high_step: %.5e " 7761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling "at which function is valid.", 7771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling solution->x, bracket_low.x, bracket_high.x); 77879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez LOG_IF(WARNING, !options().is_silent) << summary->error; 7791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return false; 7801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 7811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 78279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez VLOG(3) << "Zoom iteration: " 78379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << summary->num_iterations - num_bracketing_iterations 78479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << ", bracket_low: " << bracket_low 78579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << ", bracket_high: " << bracket_high 78679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << ", minimizing solution: " << *solution; 78779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 7881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if ((solution->value > (initial_position.value 7891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling + options().sufficient_decrease 7901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling * initial_position.gradient 7911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling * solution->x)) || 7921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling (solution->value >= bracket_low.value)) { 7931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Armijo sufficient decrease not satisfied, or not better 7941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // than current lowest sample, use as new upper bound. 7951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bracket_high = *solution; 7961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling continue; 7971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 7981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 7991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Armijo sufficient decrease satisfied, check strong Wolfe condition. 8001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (fabs(solution->gradient) <= 8011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling -options().sufficient_curvature_decrease * initial_position.gradient) { 8021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Found a valid termination point satisfying strong Wolfe conditions. 80379397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez VLOG(3) << std::scientific 80479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << std::setprecision(kErrorMessageNumericPrecision) 80579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << "Zoom phase found step size: " << solution->x 80679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez << ", satisfying strong Wolfe conditions."; 8071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling break; 8081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 8091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } else if (solution->gradient * (bracket_high.x - bracket_low.x) >= 0) { 8101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bracket_high = bracket_low; 8111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 8121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 8131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bracket_low = *solution; 8141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 8151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Solution contains a valid point which satisfies the strong Wolfe 8161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // conditions. 8171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling return true; 8181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} 8191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 8201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} // namespace internal 8211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} // namespace ceres 822