Native Line Search Algorithms

LineSearchSolution(step_size, retcode)

The result returned by a line-search solve.

Fields

• step_size: accepted step length for the current search direction.
• retcode: a SciMLBase.ReturnCode describing whether the line search found an acceptable step.

Examples

using LineSearch
using SciMLBase

sol = LineSearchSolution(0.5, SciMLBase.ReturnCode.Success)
sol.step_size
sol.retcode

NoLineSearch(; alpha = true)

Don't perform a line search. Just return the initial step length of alpha.

Examples

using LineSearch

alg = NoLineSearch(alpha = 1.0)

GoldenSection(; tol = 1e-7, maxiters = 100)

A derivative-free line search that minimizes a unimodal merit function by successively narrowing the interval containing the minimum using the golden ratio.

Keyword Arguments

• tol: interval-width tolerance used to stop the golden-section search.
• maxiters: maximum number of interval-refinement iterations.

Examples

using LineSearch

alg = GoldenSection(tol = 1e-8, maxiters = 200)

LiFukushimaLineSearch(; lambda_0 = 1, beta = 1 // 2, sigma_1 = 1 // 1000,
    sigma_2 = 1 // 1000, eta = 1 // 10, nan_maxiters::Int = 5, maxiters::Int = 100)

A derivative-free line search and global convergence of Broyden-like method for nonlinear equations [1].

Examples

using LineSearch

alg = LiFukushimaLineSearch(lambda_0 = 1.0, beta = 0.5, maxiters = 100)

RobustNonMonotoneLineSearch(; gamma = 1 // 10000, sigma_1 = 1, M::Int = 10,
    tau_min = 1 // 10, tau_max = 1 // 2, n_exp::Int = 2, maxiters::Int = 100,
    η_strategy = (fn₁, n, uₙ, fₙ) -> fn₁ / n^2)

Robust NonMonotone Line Search is a derivative free line search method from DF Sane [2].

Keyword Arguments

• M: The monotonicity of the algorithm is determined by a this positive integer. A value of 1 for M would result in strict monotonicity in the decrease of the L2-norm of the function f. However, higher values allow for more flexibility in this reduction. Despite this, the algorithm still ensures global convergence through the use of a non-monotone line-search algorithm that adheres to the Grippo-Lampariello-Lucidi condition. Values in the range of 5 to 20 are usually sufficient, but some cases may call for a higher value of M. The default setting is 10.
• gamma: a parameter that influences if a proposed step will be accepted. Higher value of gamma will make the algorithm more restrictive in accepting steps. Defaults to 1e-4.
• tau_min: if a step is rejected the new step size will get multiplied by factor, and this parameter is the minimum value of that factor. Defaults to 0.1.
• tau_max: if a step is rejected the new step size will get multiplied by factor, and this parameter is the maximum value of that factor. Defaults to 0.5.
• n_exp: the exponent of the loss, i.e. $f_n=||F(x_n)||^{n\_exp}$. The paper uses n_exp ∈ {1, 2}. Defaults to 2.
• η_strategy: function to determine the parameter η, which enables growth of $||f_n||^2$. Called as η = η_strategy(fn_1, n, x_n, f_n) with fn_1 initialized as $fn_1=||f(x_1)||^{n\_exp}$, n is the iteration number, x_n is the current x-value and f_n the current residual. Should satisfy $η > 0$ and $∑ₖ ηₖ < ∞$. Defaults to $fn_1 / n^2$.
• maxiters: the maximum number of iterations allowed for the inner loop of the algorithm. Defaults to 100.

Examples

using LineSearch

alg = RobustNonMonotoneLineSearch(M = 10, gamma = 1e-4, maxiters = 100)

BackTracking(; autodiff = nothing, c_1 = 1e-4, ρ_hi = 0.5, ρ_lo = 0.1,
    order = 3,
    maxstep = Inf, initial_alpha = true)

BackTracking line search algorithm based on the implementation in LineSearches.jl.

BackTracking specifies 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₁) such that α' ≦ ρ α.

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

autodiff is the automatic differentiation backend to use for the line search. This is only used for the derivative of the objective function at the current step size. autodiff must be specified if analytic jacobian/jvp/vjp is not available.

Examples

using ADTypes
using LineSearch

alg = BackTracking(autodiff = AutoForwardDiff(), order = 3, maxiters = 100)

StrongWolfeLineSearch(; autodiff = nothing, c1 = 1e-4, c2 = 0.9,
    α_init = 1.0, α_max = 65536.0, maxiters::Int = 10,
    zoom_maxiters::Int = 10)

Strong Wolfe line search satisfying both Armijo (sufficient decrease) and curvature conditions. Based on Nocedal & Wright, "Numerical Optimization" (2006), Algorithms 3.5 and 3.6.

Keyword Arguments

• autodiff: automatic differentiation backend used to compute directional derivatives when analytic jacobian/JVP/VJP information is unavailable.
• c1: Armijo sufficient-decrease coefficient.
• c2: curvature-condition coefficient.
• α_init: initial trial step length.
• α_max: maximum trial step length.
• maxiters: maximum iterations for the outer bracketing loop.
• zoom_maxiters: maximum iterations for the inner zoom loop.

maxiters bounds the outer bracketing loop (Alg. 3.5). zoom_maxiters bounds the inner zoom loop (Alg. 3.6) independently.

Examples

using ADTypes
using LineSearch

alg = StrongWolfeLineSearch(autodiff = AutoForwardDiff(), c1 = 1e-4, c2 = 0.9)