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
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
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
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
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 [Fletcher2013]. These are minor variations of Algorithms 3.5 and 3.6 on pages 60-61 in [Nocedal2006]. 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
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 ( ![]() ![]() |
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.