Line search routines

BackTracking(; c_1=1e-4, ρ_hi=0.5, ρ_lo=0.1, iterations=1_000, order=3, maxstep=Inf, cache=nothing)

A backtracking line-search that uses a quadratic or cubic interpolant to determine the reduction in step-size. E.g., if f(α) > f(0) + c₁ α f'(0), then the quadratic interpolant of f(0), f'(0), f(α) has a minimiser α' in the open interval (0, α). More strongly, there exists a factor ρ = ρ(c_1) such that α' ≦ ρ α.

This is a modification of the algorithm described in Nocedal Wright (2nd ed), Sec. 3.5.

HagerZhang(; delta=0.1, sigma=0.9, alphamax=Inf, rho=5.0, epsilon=1e-6,
             gamma=2/3, linesearchmax=50, psi3=0.1, display=0,
             mayterminate=Ref(false), cache=nothing, check_flatness=false)

Conjugate gradient line search implementation from:

W. W. Hager and H. Zhang (2006) Algorithm 851: CG_DESCENT, a conjugate gradient method with guaranteed descent. ACM Transactions on Mathematical Software 32: 113–137.

MoreThuente(; f_tol=1e-4, gtol=0.9, x_tol=1e-8, alphamin=1e-16,
              alphamax=65536.0, maxfev=100, cache=nothing)

The line search implementation from:

Moré, Jorge J., and David J. Thuente Line search algorithms with guaranteed sufficient decrease. ACM Transactions on Mathematical Software (TOMS) 20.3 (1994): 286-307.

Static()

A static linesearch that accepts the initial step length unchanged (no parameters to configure).

Static is intended for methods with well-scaled updates; i.e. Newton, on well-behaved problems.

StrongWolfe(; c_1=1e-4, c_2=0.9, ρ=2.0, cache=nothing)

A line search algorithm that guarantees the step length satisfies the (strong) Wolfe conditions. See Nocedal and Wright — Algorithms 3.5 and 3.6.

This algorithm is mostly of theoretical interest; users should most likely use MoreThuente, HagerZhang, or BackTracking.

Parameters (and defaults)

• c_1 = 1e-4: Armijo condition
• c_2 = 0.9 : second (strong) Wolfe condition
• ρ = 2.0 : bracket growth

cache = LineSearchCache{T}()

Initialize an empty cache for storing intermediate results during line search. The α, ϕ(α), and possibly dϕ(α) values computed during line search are available in cache.alphas, cache.values, and cache.slopes, respectively.

Example

julia> ϕ(x) = (x - π)^4; dϕ(x) = 4*(x-π)^3;

julia> cache = LineSearchCache{Float64}();

julia> ls = BackTracking(; cache);

julia> ls(ϕ, 10.0, ϕ(0), dϕ(0))
(1.8481462933284658, 2.7989406670901373)

julia> cache
LineSearchCache{Float64}([0.0, 10.0, 1.8481462933284658], [97.40909103400242, 2212.550050116452, 2.7989406670901373], [-124.02510672119926])

Because BackTracking doesn't use derivatives except at α=0, only the initial slope was stored in the cache. Other methods may store all three.