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// Interface for and implementation of various Line search algorithms. 321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#ifndef CERES_INTERNAL_LINE_SEARCH_H_ 341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#define CERES_INTERNAL_LINE_SEARCH_H_ 351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include <string> 371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include <vector> 381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/internal/eigen.h" 391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/internal/port.h" 401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include "ceres/types.h" 411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingnamespace ceres { 431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingnamespace internal { 441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingclass Evaluator; 461d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingstruct FunctionSample; 471d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// Line search is another name for a one dimensional optimization 491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// algorithm. The name "line search" comes from the fact one 501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// dimensional optimization problems that arise as subproblems of 511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// general multidimensional optimization problems. 521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// 531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// While finding the exact minimum of a one dimensionl function is 541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// hard, instances of LineSearch find a point that satisfies a 551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// sufficient decrease condition. Depending on the particular 561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// condition used, we get a variety of different line search 571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// algorithms, e.g., Armijo, Wolfe etc. 581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingclass LineSearch { 591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling public: 601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling class Function; 611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling struct Options { 631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Options() 641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling : interpolation_type(CUBIC), 651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling sufficient_decrease(1e-4), 661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling max_step_contraction(1e-3), 671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling min_step_contraction(0.9), 681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling min_step_size(1e-9), 691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling max_num_iterations(20), 701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling sufficient_curvature_decrease(0.9), 711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling max_step_expansion(10.0), 7279397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez is_silent(false), 731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling function(NULL) {} 741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Degree of the polynomial used to approximate the objective 761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // function. 771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearchInterpolationType interpolation_type; 781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Armijo and Wolfe line search parameters. 801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Solving the line search problem exactly is computationally 821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // prohibitive. Fortunately, line search based optimization 831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // algorithms can still guarantee convergence if instead of an 841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // exact solution, the line search algorithm returns a solution 851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // which decreases the value of the objective function 861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // sufficiently. More precisely, we are looking for a step_size 871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // s.t. 881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // f(step_size) <= f(0) + sufficient_decrease * f'(0) * step_size 901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double sufficient_decrease; 911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // In each iteration of the Armijo / Wolfe line search, 931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // new_step_size >= max_step_contraction * step_size 951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Note that by definition, for contraction: 971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 0 < max_step_contraction < min_step_contraction < 1 991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double max_step_contraction; 1011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // In each iteration of the Armijo / Wolfe line search, 1031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // new_step_size <= min_step_contraction * step_size 1051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Note that by definition, for contraction: 1061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 0 < max_step_contraction < min_step_contraction < 1 1081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double min_step_contraction; 1101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // If during the line search, the step_size falls below this 1121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // value, it is truncated to zero. 1131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double min_step_size; 1141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Maximum number of trial step size iterations during each line search, 1161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // if a step size satisfying the search conditions cannot be found within 1171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // this number of trials, the line search will terminate. 1181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int max_num_iterations; 1191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Wolfe-specific line search parameters. 1211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // The strong Wolfe conditions consist of the Armijo sufficient 1231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // decrease condition, and an additional requirement that the 1241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // step-size be chosen s.t. the _magnitude_ ('strong' Wolfe 1251d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // conditions) of the gradient along the search direction 1261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // decreases sufficiently. Precisely, this second condition 1271d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // is that we seek a step_size s.t. 1281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // |f'(step_size)| <= sufficient_curvature_decrease * |f'(0)| 1301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Where f() is the line search objective and f'() is the derivative 1321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // of f w.r.t step_size (d f / d step_size). 1331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double sufficient_curvature_decrease; 1341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // During the bracketing phase of the Wolfe search, the step size is 1361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // increased until either a point satisfying the Wolfe conditions is 1371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // found, or an upper bound for a bracket containing a point satisfying 1381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // the conditions is found. Precisely, at each iteration of the 1391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // expansion: 1401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // new_step_size <= max_step_expansion * step_size. 1421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // By definition for expansion, max_step_expansion > 1.0. 1441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double max_step_expansion; 1451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 14679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez bool is_silent; 14779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 1481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // The one dimensional function that the line search algorithm 1491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // minimizes. 1501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Function* function; 1511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling }; 1521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // An object used by the line search to access the function values 1541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // and gradient of the one dimensional function being optimized. 1551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // In practice, this object will provide access to the objective 1571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // function value and the directional derivative of the underlying 1581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // optimization problem along a specific search direction. 1591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // See LineSearchFunction for an example implementation. 1611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling class Function { 1621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling public: 1631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling virtual ~Function() {} 1641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Evaluate the line search objective 1651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // f(x) = p(position + x * direction) 1671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Where, p is the objective function of the general optimization 1691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // problem. 1701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // g is the gradient f'(x) at x. 1721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // f must not be null. The gradient is computed only if g is not null. 1741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling virtual bool Evaluate(double x, double* f, double* g) = 0; 1751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling }; 1761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Result of the line search. 1781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling struct Summary { 1791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Summary() 1801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling : success(false), 1811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling optimal_step_size(0.0), 1821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling num_function_evaluations(0), 1831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling num_gradient_evaluations(0), 1841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling num_iterations(0) {} 1851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bool success; 1871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double optimal_step_size; 1881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int num_function_evaluations; 1891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int num_gradient_evaluations; 1901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int num_iterations; 1911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling string error; 1921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling }; 1931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling explicit LineSearch(const LineSearch::Options& options); 1951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling virtual ~LineSearch() {} 1961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling static LineSearch* Create(const LineSearchType line_search_type, 1981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const LineSearch::Options& options, 1991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling string* error); 2001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Perform the line search. 2021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // step_size_estimate must be a positive number. 2041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // initial_cost and initial_gradient are the values and gradient of 2061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // the function at zero. 2071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // summary must not be null and will contain the result of the line 2081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // search. 2091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 2101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Summary::success is true if a non-zero step size is found. 2111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling virtual void Search(double step_size_estimate, 2121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double initial_cost, 2131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double initial_gradient, 2141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Summary* summary) = 0; 2151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double InterpolatingPolynomialMinimizingStepSize( 2161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const LineSearchInterpolationType& interpolation_type, 2171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const FunctionSample& lowerbound_sample, 2181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const FunctionSample& previous_sample, 2191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const FunctionSample& current_sample, 2201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double min_step_size, 2211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double max_step_size) const; 2221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling protected: 2241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const LineSearch::Options& options() const { return options_; } 2251d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling private: 2271d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling LineSearch::Options options_; 2281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling}; 2291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingclass LineSearchFunction : public LineSearch::Function { 2311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling public: 2321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling explicit LineSearchFunction(Evaluator* evaluator); 2331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling virtual ~LineSearchFunction() {} 2341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling void Init(const Vector& position, const Vector& direction); 235399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger virtual bool Evaluate(double x, double* f, double* g); 2361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double DirectionInfinityNorm() const; 2371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling private: 2391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Evaluator* evaluator_; 2401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Vector position_; 2411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Vector direction_; 2421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2431d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // evaluation_point = Evaluator::Plus(position_, x * direction_); 2441d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Vector evaluation_point_; 2451d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2461d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // scaled_direction = x * direction_; 2471d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Vector scaled_direction_; 2481d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Vector gradient_; 2491d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling}; 2501d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2511d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// Backtracking and interpolation based Armijo line search. This 2521d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// implementation is based on the Armijo line search that ships in the 2531d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// minFunc package by Mark Schmidt. 2541d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// 2551d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// For more details: http://www.di.ens.fr/~mschmidt/Software/minFunc.html 2561d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingclass ArmijoLineSearch : public LineSearch { 2571d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling public: 2581d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling explicit ArmijoLineSearch(const LineSearch::Options& options); 2591d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling virtual ~ArmijoLineSearch() {} 2601d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling virtual void Search(double step_size_estimate, 2611d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double initial_cost, 2621d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double initial_gradient, 2631d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Summary* summary); 2641d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling}; 2651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// Bracketing / Zoom Strong Wolfe condition line search. This implementation 2671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// is based on the pseudo-code algorithm presented in Nocedal & Wright [1] 2681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// (p60-61) with inspiration from the WolfeLineSearch which ships with the 2691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// minFunc package by Mark Schmidt [2]. 2701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// 2711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// [1] Nocedal J., Wright S., Numerical Optimization, 2nd Ed., Springer, 1999. 2721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling// [2] http://www.di.ens.fr/~mschmidt/Software/minFunc.html. 2731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberlingclass WolfeLineSearch : public LineSearch { 2741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling public: 2751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling explicit WolfeLineSearch(const LineSearch::Options& options); 2761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling virtual ~WolfeLineSearch() {} 2771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling virtual void Search(double step_size_estimate, 2781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double initial_cost, 2791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double initial_gradient, 2801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Summary* summary); 2811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Returns true iff either a valid point, or valid bracket are found. 2821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bool BracketingPhase(const FunctionSample& initial_position, 2831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double step_size_estimate, 2841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FunctionSample* bracket_low, 2851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FunctionSample* bracket_high, 2861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bool* perform_zoom_search, 2871d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Summary* summary); 2881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Returns true iff final_line_sample satisfies strong Wolfe conditions. 2891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling bool ZoomPhase(const FunctionSample& initial_position, 2901d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FunctionSample bracket_low, 2911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FunctionSample bracket_high, 2921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling FunctionSample* solution, 2931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Summary* summary); 2941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling}; 2951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} // namespace internal 2971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} // namespace ceres 2981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#endif // CERES_INTERNAL_LINE_SEARCH_H_ 300