![]() |
Reference documentation for deal.II version 9.6.0
|
Functions | |
template<typename NumberType > | |
std::optional< NumberType > | quadratic_fit (const NumberType x_low, const NumberType f_low, const NumberType g_low, const NumberType x_hi, const NumberType f_hi) |
template<typename NumberType > | |
std::optional< NumberType > | cubic_fit (const NumberType x_low, const NumberType f_low, const NumberType g_low, const NumberType x_hi, const NumberType f_hi, const NumberType g_hi) |
template<typename NumberType > | |
std::optional< NumberType > | cubic_fit_three_points (const NumberType x_low, const NumberType f_low, const NumberType g_low, const NumberType x_hi, const NumberType f_hi, const NumberType x_rec, const NumberType f_rec) |
template<typename NumberType > | |
NumberType | poly_fit (const NumberType x_low, const NumberType f_low, const NumberType g_low, const NumberType x_hi, const NumberType f_hi, const NumberType g_hi, const FiniteSizeHistory< NumberType > &x_rec, const FiniteSizeHistory< NumberType > &f_rec, const FiniteSizeHistory< NumberType > &g_rec, const std::pair< NumberType, NumberType > bounds) |
template<typename NumberType > | |
NumberType | poly_fit_three_points (const NumberType x_low, const NumberType f_low, const NumberType g_low, const NumberType x_hi, const NumberType f_hi, const NumberType g_hi, const FiniteSizeHistory< NumberType > &x_rec, const FiniteSizeHistory< NumberType > &f_rec, const FiniteSizeHistory< NumberType > &g_rec, const std::pair< NumberType, NumberType > bounds) |
template<typename NumberType > | |
std::pair< NumberType, unsigned int > | line_search (const std::function< std::pair< NumberType, NumberType >(const NumberType x)> &func, const NumberType f0, const NumberType g0, const std::function< NumberType(const NumberType x_low, const NumberType f_low, const NumberType g_low, const NumberType x_hi, const NumberType f_hi, const NumberType g_hi, const FiniteSizeHistory< NumberType > &x_rec, const FiniteSizeHistory< NumberType > &f_rec, const FiniteSizeHistory< NumberType > &g_rec, const std::pair< NumberType, NumberType > bounds)> &interpolate, const NumberType a1, const NumberType eta=0.9, const NumberType mu=0.01, const NumberType a_max=std::numeric_limits< NumberType >::max(), const unsigned int max_evaluations=20, const bool debug_output=false) |
A namespace for various algorithms related to minimization a over line.
std::optional< NumberType > LineMinimization::quadratic_fit | ( | const NumberType | x_low, |
const NumberType | f_low, | ||
const NumberType | g_low, | ||
const NumberType | x_hi, | ||
const NumberType | f_hi ) |
Given \(x\_low\) and \(x\_hi\) together with values of function \(f(x\_low)\) and \(f(x\_hi)\) and the gradient \(g(x\_low)\), return the local minimizer of the quadratic interpolation function.
The return type is optional to fit with similar functions that may not have a solution for given parameters.
std::optional< NumberType > LineMinimization::cubic_fit | ( | const NumberType | x_low, |
const NumberType | f_low, | ||
const NumberType | g_low, | ||
const NumberType | x_hi, | ||
const NumberType | f_hi, | ||
const NumberType | g_hi ) |
Given \(x\_low\) and \(x\_hi\) together with values of function \(f(x\_low)\) and \(f(x\_hi)\) and its gradients ( \(g(x\_low)*g(x\_hi) < 0\)) at those points, return the local minimizer of the cubic interpolation function (that is, the location where the cubic interpolation function attains its minimum value).
The return type is optional as the real-valued solution might not exist.
std::optional< NumberType > LineMinimization::cubic_fit_three_points | ( | const NumberType | x_low, |
const NumberType | f_low, | ||
const NumberType | g_low, | ||
const NumberType | x_hi, | ||
const NumberType | f_hi, | ||
const NumberType | x_rec, | ||
const NumberType | f_rec ) |
Find the minimizer of a cubic polynomial that goes through the points \(f\_low=f(x\_low)\), \(f\_hi=f(x\_hi)\) and \(f\_rec(x\_rec)\) and has derivatve \(g\_low\) at \(x\_low\).
The return type is optional as the real-valued solution might not exist.
NumberType LineMinimization::poly_fit | ( | const NumberType | x_low, |
const NumberType | f_low, | ||
const NumberType | g_low, | ||
const NumberType | x_hi, | ||
const NumberType | f_hi, | ||
const NumberType | g_hi, | ||
const FiniteSizeHistory< NumberType > & | x_rec, | ||
const FiniteSizeHistory< NumberType > & | f_rec, | ||
const FiniteSizeHistory< NumberType > & | g_rec, | ||
const std::pair< NumberType, NumberType > | bounds ) |
Return the minimizer of a polynomial using function values f_low
, f_hi
, and f_rec
[0] at three points x_low
, x_hi
, and x_rec
[0] as well as the derivatives at two points g_low
and g_hi
. The returned point should be within the bounds bounds
.
This function will first try to perform a cubic_fit(). If its unsuccessful, or if the minimum is not within the provided bounds
, a quadratic_fit() will be performed. The function will fallback to a bisection method if quadratic_fit() fails as well.
NumberType LineMinimization::poly_fit_three_points | ( | const NumberType | x_low, |
const NumberType | f_low, | ||
const NumberType | g_low, | ||
const NumberType | x_hi, | ||
const NumberType | f_hi, | ||
const NumberType | g_hi, | ||
const FiniteSizeHistory< NumberType > & | x_rec, | ||
const FiniteSizeHistory< NumberType > & | f_rec, | ||
const FiniteSizeHistory< NumberType > & | g_rec, | ||
const std::pair< NumberType, NumberType > | bounds ) |
Same as poly_fit(), but performing a cubic fit with three points (see cubic_fit_three_points() ).
std::pair< NumberType, unsigned int > LineMinimization::line_search | ( | const std::function< std::pair< NumberType, NumberType >(const NumberType x)> & | func, |
const NumberType | f0, | ||
const NumberType | g0, | ||
const std::function< NumberType(const NumberType x_low, const NumberType f_low, const NumberType g_low, const NumberType x_hi, const NumberType f_hi, const NumberType g_hi, const FiniteSizeHistory< NumberType > &x_rec, const FiniteSizeHistory< NumberType > &f_rec, const FiniteSizeHistory< NumberType > &g_rec, const std::pair< NumberType, NumberType > bounds)> & | interpolate, | ||
const NumberType | a1, | ||
const NumberType | eta = 0.9, | ||
const NumberType | mu = 0.01, | ||
const NumberType | a_max = std::numeric_limits< NumberType >::max(), | ||
const unsigned int | max_evaluations = 20, | ||
const bool | debug_output = false ) |
Perform a line search in \((0,max]\) with strong Wolfe conditions
\[ f(\alpha) \le f(0) + \alpha \mu f'(0) \\ |f'(\alpha)| \le \eta |f'(0)| \]
using the one dimensional function func
in conjunction with a function interpolate
to choose a new point from the interval based on the function values and derivatives at its ends. The parameter a1
is a trial estimate of the first step. Interpolation can be done using either poly_fit() or poly_fit_three_points(), or any other function that has a similar signature.
The function implements Algorithms 2.6.2 and 2.6.4 on pages 34-35 in [87]. These are minor variations of Algorithms 3.5 and 3.6 on pages 60-61 in [165]. It consists of a bracketing phase and a zoom phase, where interpolate
is used.
Two examples of use might be as follows: In the first example, we wish to find the minimum of the function \(100 * x^4 + (1-x)^2\). To find the approximate solution using line search with a polynomial fit to the curve one would perform the following steps:
In the second example, we wish to perform line search in the context of a non-linear finite element problem. What follows below is a non-optimized implementation of the back-tracking algorithm, which may be useful when the load-step size is too large. The following illustrates the basic steps necessary to utilize the scheme within the context of a global nonlinear solver:
func | A one dimensional function which returns value and derivative at the given point. |
f0 | The function value at the origin. |
g0 | The function derivative at the origin. |
interpolate | A function which determines how interpolation is done during the zoom phase. It takes values and derivatives at the current interval/bracket ( \(f\_low\), \(f\_hi\)) as well as up to 5 values and derivatives at previous steps. The returned value is to be provided within the given bounds. |
a1 | Initial trial step for the bracketing phase. |
eta | A parameter in the second Wolfe condition (curvature condition). |
mu | A parameter in the first Wolfe condition (sufficient decrease). |
a_max | The maximum allowed step size. |
max_evaluations | The maximum allowed number of function evaluations. |
debug_output | A flag to output extra debug information into the deallog static object. |
func
was called.