| 1 |
// ------------------------------------------------------------------------ |
| 2 |
// |
| 3 |
// SPDX-License-Identifier: LGPL-2.1-or-later |
| 4 |
// Copyright (C) 2018 - 2024 by the deal.II authors |
| 5 |
// |
| 6 |
// This file is part of the deal.II library. |
| 7 |
// |
| 8 |
// Part of the source code is dual licensed under Apache-2.0 WITH |
| 9 |
// LLVM-exception OR LGPL-2.1-or-later. Detailed license information |
| 10 |
// governing the source code and code contributions can be found in |
| 11 |
// LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II. |
| 12 |
// |
| 13 |
// ------------------------------------------------------------------------ |
| 14 |
|
| 15 |
#ifndef dealii_line_minimization_h |
| 16 |
#define dealii_line_minimization_h |
| 17 |
|
| 18 |
#include <deal.II/base/config.h> |
| 19 |
|
| 20 |
#include <deal.II/base/exceptions.h> |
| 21 |
#include <deal.II/base/logstream.h> |
| 22 |
#include <deal.II/base/numbers.h> |
| 23 |
#include <deal.II/base/utilities.h> |
| 24 |
|
| 25 |
#include <deal.II/numerics/history.h> |
| 26 |
|
| 27 |
#include <algorithm> |
| 28 |
#include <fstream> |
| 29 |
#include <functional> |
| 30 |
#include <limits> |
| 31 |
#include <optional> |
| 32 |
#include <string> |
| 33 |
|
| 34 |
|
| 35 |
DEAL_II_NAMESPACE_OPEN |
| 36 |
|
| 37 |
/** |
| 38 |
* A namespace for various algorithms related to minimization a over line. |
| 39 |
*/ |
| 40 |
namespace LineMinimization |
| 41 |
{ |
| 42 |
/** |
| 43 |
* Given $x\_low$ and $x\_hi$ together with values of function |
| 44 |
* $f(x\_low)$ and $f(x\_hi)$ and the gradient $g(x\_low)$, return the local |
| 45 |
* minimizer of the quadratic interpolation function. |
| 46 |
* |
| 47 |
* The return type is optional to fit with similar functions that may |
| 48 |
* not have a solution for given parameters. |
| 49 |
*/ |
| 50 |
template <typename NumberType> |
| 51 |
std::optional<NumberType> |
| 52 |
quadratic_fit(const NumberType x_low, |
| 53 |
const NumberType f_low, |
| 54 |
const NumberType g_low, |
| 55 |
const NumberType x_hi, |
| 56 |
const NumberType f_hi); |
| 57 |
|
| 58 |
/** |
| 59 |
* Given $x\_low$ and $x\_hi$ together with values of function |
| 60 |
* $f(x\_low)$ and $f(x\_hi)$ and its gradients ($g(x\_low)*g(x\_hi) < 0$) at |
| 61 |
* those points, return the local minimizer of the cubic interpolation |
| 62 |
* function (that is, the location where the cubic interpolation function |
| 63 |
* attains its minimum value). |
| 64 |
* |
| 65 |
* The return type is optional as the real-valued solution might not exist. |
| 66 |
*/ |
| 67 |
template <typename NumberType> |
| 68 |
std::optional<NumberType> |
| 69 |
cubic_fit(const NumberType x_low, |
| 70 |
const NumberType f_low, |
| 71 |
const NumberType g_low, |
| 72 |
const NumberType x_hi, |
| 73 |
const NumberType f_hi, |
| 74 |
const NumberType g_hi); |
| 75 |
|
| 76 |
/** |
| 77 |
* Find the minimizer of a cubic polynomial that goes through the |
| 78 |
* points $f\_low=f(x\_low)$, $f\_hi=f(x\_hi)$ and $f\_rec(x\_rec)$ |
| 79 |
* and has derivatve $g\_low$ at $x\_low$. |
| 80 |
* |
| 81 |
* The return type is optional as the real-valued solution might not exist. |
| 82 |
*/ |
| 83 |
template <typename NumberType> |
| 84 |
std::optional<NumberType> |
| 85 |
cubic_fit_three_points(const NumberType x_low, |
| 86 |
const NumberType f_low, |
| 87 |
const NumberType g_low, |
| 88 |
const NumberType x_hi, |
| 89 |
const NumberType f_hi, |
| 90 |
const NumberType x_rec, |
| 91 |
const NumberType f_rec); |
| 92 |
|
| 93 |
/** |
| 94 |
* Return the minimizer of a polynomial using function values @p f_low , |
| 95 |
* @p f_hi , and @p f_rec[0] at three points @p x_low , @p x_hi , and |
| 96 |
* @p x_rec[0] as well as the derivatives at two points @p g_low and @p g_hi. |
| 97 |
* The returned point should be within the bounds @p bounds . |
| 98 |
* |
| 99 |
* This function will first try to perform a cubic_fit(). If its unsuccessful, |
| 100 |
* or if the minimum is not within the provided @p bounds, a quadratic_fit() |
| 101 |
* will be performed. The function will fallback to a bisection method if |
| 102 |
* quadratic_fit() fails as well. |
| 103 |
*/ |
| 104 |
template <typename NumberType> |
| 105 |
NumberType |
| 106 |
poly_fit(const NumberType x_low, |
| 107 |
const NumberType f_low, |
| 108 |
const NumberType g_low, |
| 109 |
const NumberType x_hi, |
| 110 |
const NumberType f_hi, |
| 111 |
const NumberType g_hi, |
| 112 |
const FiniteSizeHistory<NumberType> &x_rec, |
| 113 |
const FiniteSizeHistory<NumberType> &f_rec, |
| 114 |
const FiniteSizeHistory<NumberType> &g_rec, |
| 115 |
const std::pair<NumberType, NumberType> bounds); |
| 116 |
|
| 117 |
/** |
| 118 |
* Same as poly_fit(), but performing a cubic fit with three points (see |
| 119 |
* cubic_fit_three_points() ). |
| 120 |
*/ |
| 121 |
template <typename NumberType> |
| 122 |
NumberType |
| 123 |
poly_fit_three_points(const NumberType x_low, |
| 124 |
const NumberType f_low, |
| 125 |
const NumberType g_low, |
| 126 |
const NumberType x_hi, |
| 127 |
const NumberType f_hi, |
| 128 |
const NumberType g_hi, |
| 129 |
const FiniteSizeHistory<NumberType> &x_rec, |
| 130 |
const FiniteSizeHistory<NumberType> &f_rec, |
| 131 |
const FiniteSizeHistory<NumberType> &g_rec, |
| 132 |
const std::pair<NumberType, NumberType> bounds); |
| 133 |
|
| 134 |
|
| 135 |
/** |
| 136 |
* Perform a line search in $(0,max]$ with strong Wolfe conditions |
| 137 |
* \f[ |
| 138 |
* f(\alpha) \le f(0) + \alpha \mu f'(0) \\ |
| 139 |
* |f'(\alpha)| \le \eta |f'(0)| |
| 140 |
* \f] |
| 141 |
* using the one dimensional function @p func in conjunction with a function @p interpolate |
| 142 |
* to choose a new point from the interval based on the function values and |
| 143 |
* derivatives at its ends. |
| 144 |
* The parameter @p a1 is a trial estimate of the first step. |
| 145 |
* Interpolation can be done using either poly_fit() or |
| 146 |
* poly_fit_three_points(), or any other function that has a similar |
| 147 |
* signature. |
| 148 |
* |
| 149 |
* The function implements Algorithms 2.6.2 and 2.6.4 on pages 34-35 in |
| 150 |
* @cite Fletcher2013. These are minor variations of Algorithms 3.5 |
| 151 |
* and 3.6 on pages 60-61 in @cite Nocedal2006. |
| 152 |
* It consists of a bracketing phase and a zoom phase, where @p interpolate is used. |
| 153 |
* |
| 154 |
* Two examples of use might be as follows: |
| 155 |
* In the first example, we wish to find the minimum of the function |
| 156 |
* $100 * x^4 + (1-x)^2$. To find the approximate solution using line search |
| 157 |
* with a polynomial fit to the curve one would perform the following steps: |
| 158 |
* |
| 159 |
* @code |
| 160 |
* auto func = [](const double x) |
| 161 |
* { |
| 162 |
* const double f = 100. * std::pow(x, 4) + std::pow(1. - x, 2); // Value |
| 163 |
* const double g = 400. * std::pow(x, 3) - 2. * (1. - x); // Gradient |
| 164 |
* return std::make_pair(f, g); |
| 165 |
* }; |
| 166 |
* |
| 167 |
* const auto fg0 = func(0); |
| 168 |
* const auto res = LineMinimization::line_search<double>( |
| 169 |
* func, |
| 170 |
* fg0.first, fg0.second, |
| 171 |
* LineMinimization::poly_fit<double>, |
| 172 |
* 0.1, 0.1, 0.01, 100, 20); |
| 173 |
* |
| 174 |
* const double approx_solution = res.first; |
| 175 |
* @endcode |
| 176 |
* |
| 177 |
* In the second example, we wish to perform line search in the context of a |
| 178 |
* non-linear finite element problem. What follows below is a non-optimized |
| 179 |
* implementation of the back-tracking algorithm, which may be useful when |
| 180 |
* the load-step size is too large. The following illustrates the basic steps |
| 181 |
* necessary to utilize the scheme within the context of a global nonlinear |
| 182 |
* solver: |
| 183 |
* |
| 184 |
* @code |
| 185 |
* // Solve some incremental linear system |
| 186 |
* const Vector<double> newton_update = solver_linear_system(...); |
| 187 |
* |
| 188 |
* // Now we check to see if the suggested Newton update is a good one. |
| 189 |
* // First we define what it means to perform linesearch in the context of |
| 190 |
* // this incremental nonlinear finite element problem. |
| 191 |
* auto ls_minimization_function = [&](const double step_size) |
| 192 |
* { |
| 193 |
* // Scale the full Newton update by the proposed line search step size. |
| 194 |
* Vector<double> newton_update_trial(newton_update); |
| 195 |
* newton_update_trial *= step_size; |
| 196 |
* // Ensure that the Dirichlet constraints are correctly applied, |
| 197 |
* // irrespective of the step size |
| 198 |
* constraints.distribute(newton_update_trial); |
| 199 |
* // Now add the contribution from the previously accepted solution |
| 200 |
* // history. |
| 201 |
* const Vector<double> solution_total_trial = |
| 202 |
* get_solution_total(newton_update_trial); |
| 203 |
* |
| 204 |
* // Recompute the linear system based on the trial newton update |
| 205 |
* Vector<double> system_rhs (...); |
| 206 |
* SparseMatrix<double> tangent_matrix (...); |
| 207 |
* assemble_linear_system( |
| 208 |
* tangent_matrix, system_rhs, solution_total_trial); |
| 209 |
* Vector<double> residual_trial (system_rhs); |
| 210 |
* residual_trial *= -1.0; // Residual = -RHS |
| 211 |
* |
| 212 |
* // Negelect the constrained entries in the consideration |
| 213 |
* // of the function (value and gradient) to be minimized. |
| 214 |
* constraints.set_zero(residual_trial); |
| 215 |
* |
| 216 |
* // Here we compute the function value according to the text given in |
| 217 |
* // section 5.1.4 of Wriggers, P., "Nonlinear finite element methods", |
| 218 |
* // 2008. |
| 219 |
* // The function value correspeonds to equ. 5.11 on p159. |
| 220 |
* const double f = 0.5 * (residual_trial * residual_trial); // Value |
| 221 |
* |
| 222 |
* // However, the corresponding gradient given in eq 5.14 is wrong. The |
| 223 |
* // suggested result |
| 224 |
* // const double g = -(residual_0*residual_trial); |
| 225 |
* // should actually be |
| 226 |
* // g = G(V + alpha*delta)*[ K(V + alpha*delta)*delta. |
| 227 |
* Vector<double> tmp; |
| 228 |
* tmp.reinit(newton_update); |
| 229 |
* tangent_matrix.vmult(tmp, newton_update); |
| 230 |
* const double g = tmp * residual_trial; // Gradient |
| 231 |
* |
| 232 |
* return std::make_pair(f, g); |
| 233 |
* }; |
| 234 |
* |
| 235 |
* // Next we can write a function to determine if taking the full Newton |
| 236 |
* // step is a good idea or not (i.e. if it offers good convergence |
| 237 |
* // characteristics). This function calls the one we defined above, |
| 238 |
* // and actually only performs the line search if an early exit |
| 239 |
* // criterion is not met. |
| 240 |
* auto perform_linesearch = [&]() |
| 241 |
* { |
| 242 |
* const auto res_0 = ls_minimization_function(0.0); |
| 243 |
* Assert(res_0.second < 0.0, |
| 244 |
* ExcMessage("Gradient should be negative. Current value: " + |
| 245 |
* std::to_string(res_0.second))); |
| 246 |
* const auto res_1 = ls_minimization_function(1.0); |
| 247 |
* |
| 248 |
* // Check to see if the minimum lies in the interval [0,1] through the |
| 249 |
* // values of the gradients at the limit points. |
| 250 |
* // If it does not, then the full step is accepted. This is discussed by |
| 251 |
* // Wriggers in the paragraph after equ. 5.14. |
| 252 |
* if (res_0.second * res_1.second > 0.0) |
| 253 |
* return 1.0; |
| 254 |
* |
| 255 |
* // The values for eta, mu are chosen such that more strict convergence |
| 256 |
* // conditions are enforced. |
| 257 |
* // They should be adjusted according to the problem requirements. |
| 258 |
* const double a1 = 1.0; |
| 259 |
* const double eta = 0.5; |
| 260 |
* const double mu = 0.49; |
| 261 |
* const double a_max = 1.25; |
| 262 |
* const double max_evals = 20; |
| 263 |
* const auto res = LineMinimization::line_search<double>( |
| 264 |
* ls_minimization_function, |
| 265 |
* res_0.first, res_0.second, |
| 266 |
* LineMinimization::poly_fit<double>, |
| 267 |
* a1, eta, mu, a_max, max_evals)); |
| 268 |
* |
| 269 |
* return res.first; // Final stepsize |
| 270 |
* }; |
| 271 |
* |
| 272 |
* // Finally, we can perform the line search and adjust the Newton update |
| 273 |
* // accordingly. |
| 274 |
* const double linesearch_step_size = perform_linesearch(); |
| 275 |
* if (linesearch_step_size != 1.0) |
| 276 |
* { |
| 277 |
* newton_update *= linesearch_step_size; |
| 278 |
* constraints.distribute(newton_update); |
| 279 |
* } |
| 280 |
* @endcode |
| 281 |
* |
| 282 |
* |
| 283 |
* @param func A one dimensional function which returns value and derivative |
| 284 |
* at the given point. |
| 285 |
* @param f0 The function value at the origin. |
| 286 |
* @param g0 The function derivative at the origin. |
| 287 |
* @param interpolate A function which determines how interpolation is done |
| 288 |
* during the zoom phase. It takes values and derivatives at the current |
| 289 |
* interval/bracket ($f\_low$, $f\_hi$) as well as up to 5 values and |
| 290 |
* derivatives at previous steps. The returned value is to be provided within |
| 291 |
* the given bounds. |
| 292 |
* @param a1 Initial trial step for the bracketing phase. |
| 293 |
* @param eta A parameter in the second Wolfe condition (curvature condition). |
| 294 |
* @param mu A parameter in the first Wolfe condition (sufficient decrease). |
| 295 |
* @param a_max The maximum allowed step size. |
| 296 |
* @param max_evaluations The maximum allowed number of function evaluations. |
| 297 |
* @param debug_output A flag to output extra debug information into the |
| 298 |
* <code>deallog</code> static object. |
| 299 |
* @return The function returns the step size and the number of times function |
| 300 |
* @p func was called. |
| 301 |
*/ |
| 302 |
template <typename NumberType> |
| 303 |
std::pair<NumberType, unsigned int> |
| 304 |
line_search( |
| 305 |
const std::function<std::pair<NumberType, NumberType>(const NumberType x)> |
| 306 |
&func, |
| 307 |
const NumberType f0, |
| 308 |
const NumberType g0, |
| 309 |
const std::function< |
| 310 |
NumberType(const NumberType x_low, |
| 311 |
const NumberType f_low, |
| 312 |
const NumberType g_low, |
| 313 |
const NumberType x_hi, |
| 314 |
const NumberType f_hi, |
| 315 |
const NumberType g_hi, |
| 316 |
const FiniteSizeHistory<NumberType> &x_rec, |
| 317 |
const FiniteSizeHistory<NumberType> &f_rec, |
| 318 |
const FiniteSizeHistory<NumberType> &g_rec, |
| 319 |
const std::pair<NumberType, NumberType> bounds)> &interpolate, |
| 320 |
const NumberType a1, |
| 321 |
const NumberType eta = 0.9, |
| 322 |
const NumberType mu = 0.01, |
| 323 |
const NumberType a_max = std::numeric_limits<NumberType>::max(), |
| 324 |
const unsigned int max_evaluations = 20, |
| 325 |
const bool debug_output = false); |
| 326 |
|
| 327 |
|
| 328 |
// ------------------- inline and template functions ---------------- |
| 329 |
|
| 330 |
|
| 331 |
#ifndef DOXYGEN |
| 332 |
|
| 333 |
|
| 334 |
template <typename NumberType> |
| 335 |
std::optional<NumberType> |
| 336 |
quadratic_fit(const NumberType x1, |
| 337 |
const NumberType f1, |
| 338 |
const NumberType g1, |
| 339 |
const NumberType x2, |
| 340 |
const NumberType f2) |
| 341 |
{ |
| 342 |
Assert(x1 != x2, ExcMessage("Point are the same")); |
| 343 |
const NumberType denom = (2. * g1 * x2 - 2. * g1 * x1 - 2. * f2 + 2. * f1); |
| 344 |
if (denom == 0) |
| 345 |
return {}; |
| 346 |
else |
| 347 |
return (g1 * (x2 * x2 - x1 * x1) + 2. * (f1 - f2) * x1) / denom; |
| 348 |
} |
| 349 |
|
| 350 |
|
| 351 |
|
| 352 |
template <typename NumberType> |
| 353 |
std::optional<NumberType> |
| 354 |
cubic_fit(const NumberType x1, |
| 355 |
const NumberType f1, |
| 356 |
const NumberType g1, |
| 357 |
const NumberType x2, |
| 358 |
const NumberType f2, |
| 359 |
const NumberType g2) |
| 360 |
{ |
| 361 |
Assert(x1 != x2, ExcMessage("Points are the same")); |
| 362 |
const NumberType beta1 = g1 + g2 - 3. * (f1 - f2) / (x1 - x2); |
| 363 |
const NumberType s = beta1 * beta1 - g1 * g2; |
| 364 |
if (s < 0) |
| 365 |
return {}; |
| 366 |
|
| 367 |
const NumberType beta2 = std::sqrt(s); |
| 368 |
const NumberType denom = |
| 369 |
x1 < x2 ? g2 - g1 + 2. * beta2 : g1 - g2 + 2. * beta2; |
| 370 |
if (denom == 0.) |
| 371 |
return {}; |
| 372 |
|
| 373 |
return x1 < x2 ? x2 - (x2 - x1) * (g2 + beta2 - beta1) / denom : |
| 374 |
x1 - (x1 - x2) * (g1 + beta2 - beta1) / denom; |
| 375 |
} |
| 376 |
|
| 377 |
|
| 378 |
|
| 379 |
template <typename NumberType> |
| 380 |
std::optional<NumberType> |
| 381 |
cubic_fit_three_points(const NumberType x1, |
| 382 |
const NumberType f1, |
| 383 |
const NumberType g1, |
| 384 |
const NumberType x2, |
| 385 |
const NumberType f2, |
| 386 |
const NumberType x3, |
| 387 |
const NumberType f3) |
| 388 |
{ |
| 389 |
Assert(x1 != x2, ExcMessage("Points are the same")); |
| 390 |
Assert(x1 != x3, ExcMessage("Points are the same")); |
| 391 |
// f(x) = A *(x-x1)^3 + B*(x-x1)^2 + C*(x-x1) + D |
| 392 |
// => |
| 393 |
// D = f1 |
| 394 |
// C = g1 |
| 395 |
|
| 396 |
// the rest is a system of 2 equations: |
| 397 |
|
| 398 |
const NumberType x2_shift = x2 - x1; |
| 399 |
const NumberType x3_shift = x3 - x1; |
| 400 |
const NumberType r1 = f2 - f1 - g1 * x2_shift; |
| 401 |
const NumberType r2 = f3 - f1 - g1 * x3_shift; |
| 402 |
const NumberType denom = |
| 403 |
Utilities::fixed_power<2>(x2_shift * x3_shift) * (x2_shift - x3_shift); |
| 404 |
if (denom == 0.) |
| 405 |
return {}; |
| 406 |
|
| 407 |
const NumberType A = (r1 * Utilities::fixed_power<2>(x3_shift) - |
| 408 |
r2 * Utilities::fixed_power<2>(x2_shift)) / |
| 409 |
denom; |
| 410 |
const NumberType B = (r2 * Utilities::fixed_power<3>(x2_shift) - |
| 411 |
r1 * Utilities::fixed_power<3>(x3_shift)) / |
| 412 |
denom; |
| 413 |
const NumberType &C = g1; |
| 414 |
|
| 415 |
// now get the minimizer: |
| 416 |
const NumberType radical = B * B - A * C * 3; |
| 417 |
if (radical < 0) |
| 418 |
return {}; |
| 419 |
|
| 420 |
return x1 + (-B + std::sqrt(radical)) / (A * 3); |
| 421 |
} |
| 422 |
|
| 423 |
|
| 424 |
|
| 425 |
template <typename NumberType> |
| 426 |
NumberType |
| 427 |
poly_fit(const NumberType x1, |
| 428 |
const NumberType f1, |
| 429 |
const NumberType g1, |
| 430 |
const NumberType x2, |
| 431 |
const NumberType f2, |
| 432 |
const NumberType g2, |
| 433 |
const FiniteSizeHistory<NumberType> &, |
| 434 |
const FiniteSizeHistory<NumberType> &, |
| 435 |
const FiniteSizeHistory<NumberType> &, |
| 436 |
const std::pair<NumberType, NumberType> bounds) |
| 437 |
{ |
| 438 |
Assert(bounds.first < bounds.second, ExcMessage("Incorrect bounds")); |
| 439 |
|
| 440 |
// Similar to scipy implementation but we fit based on two points |
| 441 |
// with their gradients and do bisection on bounds. |
| 442 |
// https://github.com/scipy/scipy/blob/v1.0.0/scipy/optimize/linesearch.py#L555-L563 |
| 443 |
|
| 444 |
// First try cubic interpolation |
| 445 |
std::optional<NumberType> res = cubic_fit(x1, f1, g1, x2, f2, g2); |
| 446 |
if (res && *res >= bounds.first && *res <= bounds.second) |
| 447 |
return *res; |
| 448 |
|
| 449 |
// cubic either fails or outside of safe region, do quadratic: |
| 450 |
res = quadratic_fit(x1, f1, g1, x2, f2); |
| 451 |
if (res && *res >= bounds.first && *res <= bounds.second) |
| 452 |
return *res; |
| 453 |
|
| 454 |
// quadratic either failed or outside of safe region. Do bisection |
| 455 |
// on safe region |
| 456 |
return (bounds.first + bounds.second) * 0.5; |
| 457 |
} |
| 458 |
|
| 459 |
|
| 460 |
|
| 461 |
template <typename NumberType> |
| 462 |
NumberType |
| 463 |
poly_fit_three_points(const NumberType x1, |
| 464 |
const NumberType f1, |
| 465 |
const NumberType g1, |
| 466 |
const NumberType x2, |
| 467 |
const NumberType f2, |
| 468 |
const NumberType /*g2*/, |
| 469 |
const FiniteSizeHistory<NumberType> &x_rec, |
| 470 |
const FiniteSizeHistory<NumberType> &f_rec, |
| 471 |
const FiniteSizeHistory<NumberType> & /*g_rec*/, |
| 472 |
const std::pair<NumberType, NumberType> bounds) |
| 473 |
{ |
| 474 |
Assert(bounds.first < bounds.second, ExcMessage("Incorrect bounds")); |
| 475 |
AssertDimension(x_rec.size(), f_rec.size()); |
| 476 |
|
| 477 |
// Same as scipy implementation where cubic fit is using 3 points |
| 478 |
// https://github.com/scipy/scipy/blob/v1.0.0/scipy/optimize/linesearch.py#L555-L563 |
| 479 |
|
| 480 |
// First try cubic interpolation after first iteration |
| 481 |
std::optional<NumberType> res = |
| 482 |
x_rec.size() > 0 ? |
| 483 |
cubic_fit_three_points(x1, f1, g1, x2, f2, x_rec[0], f_rec[0]) : |
| 484 |
std::optional<NumberType>{}; |
| 485 |
if (res && *res >= bounds.first && *res <= bounds.second) |
| 486 |
return *res; |
| 487 |
|
| 488 |
// cubic either fails or outside of safe region, do quadratic: |
| 489 |
res = quadratic_fit(x1, f1, g1, x2, f2); |
| 490 |
if (res && *res >= bounds.first && *res <= bounds.second) |
| 491 |
return *res; |
| 492 |
|
| 493 |
// quadratic either failed or outside of safe region. Do bisection |
| 494 |
// on safe region |
| 495 |
return (bounds.first + bounds.second) * 0.5; |
| 496 |
} |
| 497 |
|
| 498 |
|
| 499 |
|
| 500 |
template <typename NumberType> |
| 501 |
std::pair<NumberType, unsigned int> |
| 502 |
line_search( |
| 503 |
const std::function<std::pair<NumberType, NumberType>(const NumberType x)> |
| 504 |
&func, |
| 505 |
const NumberType f0, |
| 506 |
const NumberType g0, |
| 507 |
const std::function< |
| 508 |
NumberType(const NumberType x_low, |
| 509 |
const NumberType f_low, |
| 510 |
const NumberType g_low, |
| 511 |
const NumberType x_hi, |
| 512 |
const NumberType f_hi, |
| 513 |
const NumberType g_hi, |
| 514 |
const FiniteSizeHistory<NumberType> &x_rec, |
| 515 |
const FiniteSizeHistory<NumberType> &f_rec, |
| 516 |
const FiniteSizeHistory<NumberType> &g_rec, |
| 517 |
const std::pair<NumberType, NumberType> bounds)> &choose, |
| 518 |
const NumberType a1, |
| 519 |
const NumberType eta, |
| 520 |
const NumberType mu, |
| 521 |
const NumberType a_max, |
| 522 |
const unsigned int max_evaluations, |
| 523 |
const bool debug_output) |
| 524 |
{ |
| 525 |
// Note that scipy use dcsrch() from Minpack2 Fortran lib for line search |
| 526 |
Assert(mu < 0.5 && mu > 0, ExcMessage("mu is not in (0,1/2).")); |
| 527 |
Assert(eta < 1. && eta > mu, ExcMessage("eta is not in (mu,1).")); |
| 528 |
Assert(a_max > 0, ExcMessage("max is not positive.")); |
| 529 |
Assert(a1 > 0 && a1 <= a_max, ExcMessage("a1 is not in (0,max].")); |
| 530 |
Assert(g0 < 0, ExcMessage("Initial slope is not negative")); |
| 531 |
|
| 532 |
// Growth parameter for bracketing phase: |
| 533 |
// 1 < tau1 |
| 534 |
const NumberType tau1 = 9.; |
| 535 |
// shrink parameters for sectioning phase to prevent ai from being |
| 536 |
// arbitrary close to the extremes of the interval. |
| 537 |
// 0 < tau2 < tau3 <= 1/2 |
| 538 |
// tau2 <= eta is advisable |
| 539 |
const NumberType tau2 = 0.1; // bound for closeness to a_lo |
| 540 |
const NumberType tau3 = 0.5; // bound for closeness to a_hi |
| 541 |
|
| 542 |
const NumberType g0_abs = std::abs(g0); |
| 543 |
const NumberType f_min = f0 + a_max * mu * g0; |
| 544 |
|
| 545 |
// return True if the first Wolfe condition (sufficient decrease) is |
| 546 |
// satisfied |
| 547 |
const auto w1 = [&](const NumberType a, const NumberType f) { |
| 548 |
return f <= f0 + a * mu * g0; |
| 549 |
}; |
| 550 |
|
| 551 |
// return True if the second Wolfe condition (curvature condition) is |
| 552 |
// satisfied |
| 553 |
const auto w2 = [&](const NumberType g) { |
| 554 |
return std::abs(g) <= eta * g0_abs; |
| 555 |
}; |
| 556 |
|
| 557 |
// Bracketing phase (Algorithm 2.6.2): look for a non-trivial interval |
| 558 |
// which is known to contain an interval of acceptable points. |
| 559 |
// We adopt notation of Noceal. |
| 560 |
const NumberType x = std::numeric_limits<NumberType>::signaling_NaN(); |
| 561 |
NumberType a_lo = x, f_lo = x, g_lo = x; |
| 562 |
NumberType a_hi = x, f_hi = x, g_hi = x; |
| 563 |
NumberType ai = x, fi = x, gi = x; |
| 564 |
|
| 565 |
// count function calls in i: |
| 566 |
unsigned int i = 0; |
| 567 |
{ |
| 568 |
NumberType f_prev, g_prev, a_prev; |
| 569 |
ai = a1; |
| 570 |
f_prev = f0; |
| 571 |
g_prev = g0; |
| 572 |
a_prev = 0; |
| 573 |
|
| 574 |
while (i < max_evaluations) |
| 575 |
{ |
| 576 |
const auto fgi = func(ai); |
| 577 |
fi = fgi.first; |
| 578 |
gi = fgi.second; |
| 579 |
++i; |
| 580 |
|
| 581 |
if (debug_output) |
| 582 |
deallog << "Bracketing phase: " << i << std::endl |
| 583 |
<< ai << ' ' << fi << ' ' << gi << ' ' << w1(ai, fi) << ' ' |
| 584 |
<< w2(gi) << ' ' << f_min << std::endl; |
| 585 |
|
| 586 |
// first check if we can stop bracketing or the whole line search: |
| 587 |
if (fi <= f_min || ai == a_max) |
| 588 |
{ |
| 589 |
if (debug_output) |
| 590 |
deallog << "Reached the maximum step size." << std::endl; |
| 591 |
return std::make_pair(ai, i); |
| 592 |
} |
| 593 |
|
| 594 |
if (!w1(ai, fi) || |
| 595 |
(fi >= f_prev && i > 1)) // violate first Wolfe or not descending |
| 596 |
{ |
| 597 |
a_lo = a_prev; |
| 598 |
f_lo = f_prev; |
| 599 |
g_lo = g_prev; |
| 600 |
|
| 601 |
a_hi = ai; |
| 602 |
f_hi = fi; |
| 603 |
g_hi = gi; |
| 604 |
break; // end bracketing |
| 605 |
} |
| 606 |
|
| 607 |
if (w2(gi)) // satisfies both Wolfe conditions |
| 608 |
{ |
| 609 |
if (debug_output) |
| 610 |
deallog << "Satisfied both Wolfe conditions during Bracketing." |
| 611 |
<< std::endl; |
| 612 |
|
| 613 |
Assert(w1(ai, fi), ExcInternalError()); |
| 614 |
return std::make_pair(ai, i); |
| 615 |
} |
| 616 |
|
| 617 |
if (gi >= 0) // not descending |
| 618 |
{ |
| 619 |
a_lo = ai; |
| 620 |
f_lo = fi; |
| 621 |
g_lo = gi; |
| 622 |
|
| 623 |
a_hi = a_prev; |
| 624 |
f_hi = f_prev; |
| 625 |
g_hi = g_prev; |
| 626 |
break; // end bracketing |
| 627 |
} |
| 628 |
|
| 629 |
// extrapolation step with the bounds |
| 630 |
const auto bounds = |
| 631 |
std::make_pair(2. * ai - a_prev, |
| 632 |
std::min(a_max, ai + tau1 * (ai - a_prev))); |
| 633 |
|
| 634 |
a_prev = ai; |
| 635 |
f_prev = fi; |
| 636 |
g_prev = gi; |
| 637 |
|
| 638 |
// NOTE: Fletcher's 2.6.2 includes optional extrapolation, we |
| 639 |
// simply take the upper bound |
| 640 |
// Scipy increases by factor of two: |
| 641 |
// https://github.com/scipy/scipy/blob/v1.0.0/scipy/optimize/linesearch.py#L447 |
| 642 |
ai = bounds.second; |
| 643 |
} |
| 644 |
} |
| 645 |
|
| 646 |
AssertThrow( |
| 647 |
i < max_evaluations, |
| 648 |
ExcMessage( |
| 649 |
"Could not find the initial bracket within the given number of iterations.")); |
| 650 |
|
| 651 |
// Check properties of the bracket (Theorem 3.2 in More and Thuente, 94 |
| 652 |
// and Eq. 2.6.3 in Fletcher 2013 |
| 653 |
|
| 654 |
// FIXME: these conditions are actually violated for Fig3 and a1=10^3 in |
| 655 |
// More and Thorenton, 94. |
| 656 |
|
| 657 |
/* |
| 658 |
Assert((f_lo < f_hi) && w1(a_lo, f_lo), ExcInternalError()); |
| 659 |
Assert(((a_hi - a_lo) * g_lo < 0) && !w2(g_lo), ExcInternalError()); |
| 660 |
Assert((w1(a_hi, f_hi) || f_hi >= f_lo), ExcInternalError()); |
| 661 |
*/ |
| 662 |
|
| 663 |
// keep short history of last points to improve interpolation |
| 664 |
FiniteSizeHistory<NumberType> a_rec(5), f_rec(5), g_rec(5); |
| 665 |
// if neither a_lo nor a_hi are zero: |
| 666 |
if (std::abs(a_lo) > std::numeric_limits<NumberType>::epsilon() && |
| 667 |
std::abs(a_hi) > std::numeric_limits<NumberType>::epsilon()) |
| 668 |
{ |
| 669 |
a_rec.add(0); |
| 670 |
f_rec.add(f0); |
| 671 |
g_rec.add(g0); |
| 672 |
} |
| 673 |
|
| 674 |
// Now sectioning phase: we allow both [a_lo, a_hi] and [a_hi, a_lo] |
| 675 |
while (i < max_evaluations) |
| 676 |
{ |
| 677 |
const NumberType a_lo_safe = a_lo + tau2 * (a_hi - a_lo); |
| 678 |
const NumberType a_hi_safe = a_hi - tau3 * (a_hi - a_lo); |
| 679 |
const auto bounds = std::minmax(a_lo_safe, a_hi_safe); |
| 680 |
|
| 681 |
ai = choose( |
| 682 |
a_lo, f_lo, g_lo, a_hi, f_hi, g_hi, a_rec, f_rec, g_rec, bounds); |
| 683 |
|
| 684 |
const std::pair<NumberType, NumberType> fgi = func(ai); |
| 685 |
fi = fgi.first; |
| 686 |
gi = fgi.second; |
| 687 |
++i; |
| 688 |
|
| 689 |
if (debug_output) |
| 690 |
deallog << "Sectioning phase: " << i << std::endl |
| 691 |
<< a_lo << ' ' << f_lo << ' ' << g_lo << ' ' << w1(a_lo, f_lo) |
| 692 |
<< ' ' << w2(g_lo) << std::endl |
| 693 |
<< a_hi << ' ' << f_hi << ' ' << g_hi << ' ' << w1(a_hi, f_hi) |
| 694 |
<< ' ' << w2(g_hi) << std::endl |
| 695 |
<< ai << ' ' << fi << ' ' << gi << ' ' << w1(ai, fi) << ' ' |
| 696 |
<< w2(gi) << std::endl; |
| 697 |
|
| 698 |
if (!w1(ai, fi) || fi >= f_lo) |
| 699 |
// take [a_lo, ai] |
| 700 |
{ |
| 701 |
a_rec.add(a_hi); |
| 702 |
f_rec.add(f_hi); |
| 703 |
g_rec.add(g_hi); |
| 704 |
|
| 705 |
a_hi = ai; |
| 706 |
f_hi = fi; |
| 707 |
g_hi = gi; |
| 708 |
} |
| 709 |
else |
| 710 |
{ |
| 711 |
if (w2(gi)) // satisfies both wolf |
| 712 |
{ |
| 713 |
if (debug_output) |
| 714 |
deallog << "Satisfied both Wolfe conditions." << std::endl; |
| 715 |
Assert(w1(ai, fi), ExcInternalError()); |
| 716 |
return std::make_pair(ai, i); |
| 717 |
} |
| 718 |
|
| 719 |
if (gi * (a_hi - a_lo) >= 0) |
| 720 |
// take [ai, a_lo] |
| 721 |
{ |
| 722 |
a_rec.add(a_hi); |
| 723 |
f_rec.add(f_hi); |
| 724 |
g_rec.add(g_hi); |
| 725 |
|
| 726 |
a_hi = a_lo; |
| 727 |
f_hi = f_lo; |
| 728 |
g_hi = g_lo; |
| 729 |
} |
| 730 |
else |
| 731 |
// take [ai, a_hi] |
| 732 |
{ |
| 733 |
a_rec.add(a_lo); |
| 734 |
f_rec.add(f_lo); |
| 735 |
g_rec.add(g_lo); |
| 736 |
} |
| 737 |
|
| 738 |
a_lo = ai; |
| 739 |
f_lo = fi; |
| 740 |
g_lo = gi; |
| 741 |
} |
| 742 |
} |
| 743 |
|
| 744 |
// if we got here, we could not find the solution |
| 745 |
AssertThrow( |
| 746 |
false, |
| 747 |
ExcMessage( |
| 748 |
"Could not could complete the sectioning phase within the given number of iterations.")); |
| 749 |
return std::make_pair(std::numeric_limits<NumberType>::signaling_NaN(), i); |
| 750 |
} |
| 751 |
|
| 752 |
#endif // DOXYGEN |
| 753 |
|
| 754 |
} // namespace LineMinimization |
| 755 |
|
| 756 |
DEAL_II_NAMESPACE_CLOSE |
| 757 |
|
| 758 |
#endif // dealii_line_minimization_h |