Native Line Search Algorithms

LineSearchSolution(step_size, retcode)
LineSearchSolution(step_size, retcode, ϕ, dϕ)

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.
• ϕ: merit value at step_size, or nothing if the algorithm did not report it. Returning it lets the caller reuse the accepted point instead of re-evaluating the objective, which for an AD-defined problem is a full derivative pass per outer iteration.
• dϕ: directional derivative at step_size, or nothing.

Examples

using LineSearch
using SciMLBase

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

AbstractMerit

Supertype for the scalar function a line search reduces along the ray u + α ⋅ du.

A line search algorithm is merit-agnostic: it consumes ϕ(α) and ϕ'(α) and knows nothing about where they came from. The merit is the only thing that differs between the two callers:

Keeping this distinction out of the algorithms is what lets one implementation of Hager–Zhang or Moré–Thuente serve both NonlinearProblems and OptimizationProblems.

ResidualMerit()

Merit ϕ(α) = ‖F(u + α du)‖² / 2 for root finding. The directional derivative ⟨F, J ⋅ du⟩ requires a Jacobian-vector product.

ObjectiveMerit()

Merit ϕ(α) = f(u + α du) for optimization, where f is the objective itself.

The directional derivative is ⟨∇f, du⟩ — a dot product against a gradient the optimizer has typically already computed, rather than the Hessian-vector product that ResidualMerit would require if pointed at ∇f = 0.

set_initial_step!(cache, α)

Set the first trial step length used by the next solve!.

Quasi-Newton methods need this per iteration: the unit step is the right first guess once curvature information has accumulated, but not on the first iteration, where the direction is plain steepest descent and has no natural scale. Algorithms that ignore the initial step leave this a no-op.

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)

ArmijoLineSearch(; autodiff = nothing, c_1 = 1e-4, contraction = 0.5,
    initial_alpha = 1, maxiters = 40)

Geometric Armijo backtracking [3]. Starting from initial_alpha, multiply the step by contraction until the finite merit value satisfies ϕ(α) ≤ ϕ(0) + c_1 * α * ϕ'(0), for at most maxiters trials. The starting directional derivative must be finite and strictly negative. Unlike BackTracking, this method does not interpolate trial values. It enforces sufficient decrease only, so methods requiring a Wolfe curvature condition should select a Wolfe search instead.

Uses the same init signatures as BackTracking. autodiff supplies the derivative backend for nonlinear problems without analytic derivatives. Call solve!(cache, u, du; ϕ0 = nothing, dϕ0 = nothing, gradient = nothing) to reuse an existing starting merit and directional derivative (or merit gradient). If the caller always supplies the derivative, pass need_deriv = false to init to avoid constructing a derivative operator. This also permits objective-only OptimizationFunctions.

set_initial_step! controls the next search's first step, and get_trial returns its cached point and residual after success. For box projection, use ProjectedBackTracking.

ProjectedBackTracking(; c_1 = 1e-4, contraction = 0.5,
    initial_alpha = 1, maxiters = 40)

Armijo backtracking along the box-projected path P(u + α * du). Initialize with init(prob, alg, fu, u; lb = prob.lb, ub = prob.ub) for a nonlinear problem, or init(prob, alg, u; lb = prob.lb, ub = prob.ub) for an optimization problem. Bounds may be scalars, arrays with the same axes as u, or nothing (unbounded). They are rounded inward to the state element type to keep trial evaluations feasible. The starting point must be feasible and the state must be real floating point.

Call solve!(cache, u, du; gradient, ϕ0 = nothing) with the merit gradient at u: J' * fu for residual merit, or the objective gradient for optimization. Supplying ϕ0 avoids evaluating the starting merit. No derivative operator is constructed. A trial is accepted when its finite merit satisfies ϕ(trial) ≤ ϕ0 + c_1 * dot(gradient, trial - u) with a strictly negative slope. Each rejection multiplies α by contraction, for at most maxiters trials.

Use get_trial after a successful solve to retrieve the projected point and cached residual. Applying u + sol.step_size * du alone does not project the step. Cache storage is reused across searches; reinit!(cache; p) updates parameters and resets the initial step, and set_initial_step! changes the next search's initial step. Bounds are fixed for the lifetime of the cache.

This is the Armijo rule along the projection arc [4]. With a general supplied direction it is a sufficient-decrease search; convergence also depends on the outer method producing suitable descent directions.

get_trial(cache)

Return (u = trial_point, fu = trial_residual) from the most recent successful ArmijoLineSearch or ProjectedBackTracking solve. fu is nothing for optimization problems. The returned arrays alias cache storage and may be overwritten by the next search; copy them if they must remain available. The result is unspecified after a failed search.

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.

Merit function

The static path (SArray or Number states, usable inside GPU kernels) and the allocating path share the same merit by problem type:

• AbstractNonlinearProblem uses the residual merit ½‖f(u)‖².
• OptimizationProblem uses the objective f(u) directly, with gradient from prob.f.grad (out-of-place grad(u, p) on the OptimizationFunction). SArray/Number is allocation-free; other states (e.g. Vector) allocate.

Examples

using ADTypes
using LineSearch

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

HagerZhangLineSearch(; autodiff = nothing, δ = 0.1, σ = 0.9, ε = 1e-6,
    θ = 0.5, ρ = 5.0, maxiters = 50, α_init = 1.0, α_max = Inf)

Hager–Zhang line search (Hager & Zhang, SIAM J. Optim. 16(1), 2005; CG_DESCENT, ACM TOMS 32(1), 2006).

Accepts a step satisfying either the original Wolfe conditions or the approximate Wolfe conditions

σ ϕ'(0) ≤ ϕ'(α) ≤ (2δ - 1) ϕ'(0),    ϕ(α) ≤ ϕ(0) + ε_k

The approximate conditions stay testable once ϕ(α) - ϕ(0) has fallen to the level of floating-point roundoff, which is exactly where the original conditions become unsatisfiable — near a minimizer. A search restricted to the original conditions stalls there, above the gradient floor.

Works with both merits: pass a NonlinearProblem for ‖F‖²/2 or an OptimizationProblem for the objective itself.

Keyword Arguments

• autodiff: AD backend for the directional derivative. Only consulted for the residual merit, which needs a Jacobian-vector product; the objective merit uses the gradient directly.
• δ: sufficient-decrease coefficient, 0 < δ < 1/2.
• σ: curvature coefficient, δ ≤ σ < 1.
• ε: sets ε_k = ε |ϕ(0)|, the roundoff-level slack in the approximate conditions.
• θ: bisection weight used when an interval must be shrunk.
• ρ: expansion factor used while bracketing.
• maxiters: cap on outer iterations, bracket expansions, and bisections.
• α_init, α_max: initial and maximum step length.

Examples

using LineSearch

alg = HagerZhangLineSearch(δ = 0.1, σ = 0.9)

MoreThuenteLineSearch(; autodiff = nothing, ftol = 1e-4, gtol = 0.9,
    xtol = 1e-10, α_init = 1.0, α_min = 0.0, α_max = Inf, maxiters = 50)

Moré–Thuente line search satisfying the strong Wolfe conditions, following the MINPACK-2 dcsrch/dcstep formulation (Moré & Thuente, ACM TOMS 20(3), 1994).

Uses safeguarded cubic/quadratic interpolation and, during its first stage, minimizes the auxiliary function ψ(α) = ϕ(α) - ϕ(0) - ftol α ϕ'(0) rather than ϕ itself, which is what lets it locate a strong-Wolfe point in very few evaluations on well-scaled problems.

Because it enforces the original strong Wolfe conditions, it stalls once ϕ(α) - ϕ(0) reaches roundoff; prefer HagerZhangLineSearch when iterating to tight tolerances.

Works with both merits: pass a NonlinearProblem for ‖F‖²/2 or an OptimizationProblem for the objective itself.

Keyword Arguments

• autodiff: AD backend for the directional derivative under the residual merit; unused for the objective merit.
• ftol: sufficient-decrease coefficient.
• gtol: curvature coefficient for |ϕ'(α)| ≤ gtol |ϕ'(0)|.
• xtol: relative width at which a bracketed interval is deemed converged.
• α_init, α_min, α_max: initial step and bounds.
• maxiters: maximum function evaluations.

Examples

using LineSearch

alg = MoreThuenteLineSearch(ftol = 1e-4, gtol = 0.1)