AbstractOptBuffer

Abstract type for buffers used to implement optimizations routines (including stopping criteria etc.)

BFGS

Quasi-Newton descent method.

BasicConvergenceStats

Wrapper type to provide basic stop conditions: magnitude of gradient is less than the specified value, objective function call count exceeds threshold, iteration count exceeds threshold.

CGDescent

Conjugate gradient method (Hager-Zhang version [W.Hager, H.Zhang // SIAM J. Optim (2006) Vol. 16, pp. 170-192])

CholBFGS

Quasi-Newton descent method.

ConstrainStepSize

Wrapper type to limit step sizes attempted in optimization, given a function (origin, direction) -> max_step.

FixedRateDescent

Descent method which minimizes the objective function in the direction of antigradient at each step.

HyperGradDescent

Descent method which minimizes the objective function in the direction of antigradient at each step.

MomentumDescent

Descent method which minimizes the objective function in the direction of antigradient at each step.

NesterovMomentum

Descent method which minimizes the objective function in the direction of antigradient at each step.

OptBuffer

Abstract type for structs designed to store the data required for core optimization logic.

SteepestDescent

Descent method which minimizes the objective function in the direction of antigradient at each step.

Wrapper

Abstract type for wrappers around core buffers meant for auxiliary purposes (stopping conditions, logging etc.)

argumentvec(M::AbstractOptBuffer)

Return the argument vector at the end of the optimization step.

base_method(M::AbstractOptBuffer)

For a Wrapper object, return the wrapped buffer. For an OptBuffer object, return the object itself.

callfn!(fdf, M::AbstractOptBuffer, x, α, d)

Return the value of fdf(x + α * d) overwriting the internal buffers of M as needed. fdf(x, g) must return a tuple (f(x), ∇f(x)) and, if g is mutable, overwrite it with the gradient (see optimize!).

conv_success(M::AbstractOptBuffer)

Decide if the optimization has converged from the state of M (useful to distinguish between stopping by convergence and stopping by iterations count when the convergence has been achieved on the limiting iteration).

convstat(M::Wrapper)

For a converged state, return the statistics in the form of NamedTuple (converged = true/false, argument, gradient, iterations, calls). Negative values of calls or iterations mean that the number has not been tracked.

fnval(M::AbstractOptBuffer)

Return the objective function value at the end of the optimization step.

fnval_origin(M::AbstractOptBuffer)

Return the objective function value at the start of the optimization step.

gradientvec(M::AbstractOptBuffer)

Return the gradient vector at the end of the optimization step.

optfn! must be the 3-arg closure that computes fdf(x + α*d) and overwrites M's gradient

mcholesky!(A::AbstractMatrix)

Perform an in-place modified Cholesky decomposition on matrix A (Gill, Murray, Wright, Practical optimization (1981), p.111)

optimize!(
    fdf, M::OptBuffer, x₀;
    gtol=1e-6,
    convcond=nothing,
    maxiter=100,
    maxcalls=nothing,
    reset=true,
    constrain_step=nothing,
    tracking=nothing,
    verbosity=0
)

Find an optimizer for fdf, starting with the initial approximation x₀.

Arguments

• M::OptBuffer: the core method to use for optimization
• fdf(x, g)::Function: function to optimize. It must return a tuple (f(x), ∇f(x)) and, if g is mutable, overwrite it with the gradient.
• x0: initial approximation

Keywords

Convergence criteria

There are two options to specify convergence criterion. The default is by gtol and the second by custom stop convcond.

• gtol::Real: (default stop criterion) stop optimization when the gradient's 2-norm is less
• convcond=(x, xpre, y, ypre, g)->Bool: function, custom stop criterion based on argument values, function values and gradient. If nothing (default), corresponds to gtol, and when specified, the gtol-criterion is ignored.

Example (default criterion): convcond = (x, xpre, y, ypre, g) -> norm(g, 2) ≤ gtol.

Limitting optimization

(Un)Limit optimization process by specifing either maxiter and/or maxcalls.

• maxiter::Integer: force stop optimization after this number of iterations (use nothing or a negative value to not constrain iteration number)
• maxcalls::Integer: force stop optimization after this number of function calls (use nothing or a negative value to not constrain call number)

Optimization constrains

The inequality constrains of optimization is handled by constrain_step.

• constrain_step(x0, d): a function to constrain step from x0 in the direction d. It must return a real-numbered value α such that x0 + αd is the maximum allowed step

Initializing

• reset=true: a value to pass as a keyword argument to the optimizer init! method

Optimization path

• tracking::Union{Nothing,IO,AbstractString}: IO stream or a file name to log the optimization process or nothing to disable logging (default: nothing)
• verbosity::Integer: verbosity of logging. 0 (default) disables tracking. 1 logs all points of objective function evaluation with corresponding values and gradients. 2 shows additional statistics regarding the line search. Option ignored if tracking == nothing.

optimize!(fdf, M::Wrapper, x0)

Find an optimizer for fdf, starting with the initial approximation x0. fdf(x, g) must return a tuple (f(x), ∇f(x)) and, if g is mutable, overwrite it with the gradient.

optimize(
    fdf, x₀;
    method,
    kw...
)

Find an optimizer for fdf, starting with the initial approximation x₀. method keyword chooses a specific optimization method. See optimize! for the description of other keywords.

reset!(M::AbstractOptBuffer, args...; kwargs...)

Reset the solver parameters to the default (or to specific value – see the documentation for the specific types).

Each method has to implement a parameter-free reset!(M) method.

Downhill.solver(
    M::OptBuffer;
    gtol = 1e-6,
    maxiter = 100,
    maxcalls = nothing,
    constrain_step=nothing,
)

Return the wrapper object for a chosen method to solve an optimization problem with given parameters. For the description of keywords, see optimize!

Downhill.solver(
    M::DataType, x;
    gtol=1e-6, maxiter = 100, maxcalls = nothing, constrain_step)

Return the wrapper object for a chosen method to solve an optimization problem with given parameters compatible with the dimensions of x.

sqmatr(vec::AbstractVector, [element_type = eltype(vec)])

Create an uninitialized mutable N×N matrix with the given element type, given a vector of length N.

step!(fdf, M::AbstractOptBuffer; kw...)

Make one iteration of optimization routine from the current state of M using fdf as the objective function and modifying the internal buffers as needed.

step_origin(M::AbstractOptBuffer)

Return the argument vector at the start of the optimization step.

stopcond(M::AbstractOptBuffer)

Decide if the optimization should be stopped from the state of M.

DescentMethods.strong_backtracking!(fdf, x₀, d, [y₀, g₀]; [α, αmax, β, σ])

Find α such that f(x₀ + αd) ≤ f(x₀) + β α d⋅∇f(x) and |d⋅∇f(x₀ + αd)| ≤ σ|d⋅∇f(x₀)| (strong Wolfe conditions) using the backtracking line search with cubic interpolation and Hager-Zhang approximation when steps are very small. Optionally, y₀ = f(x₀) and g₀ = ∇f(x₀) may be provided to avoid recalculation.

Arguments

• fdf: a function fdf(x, α, d) returning a tuple f(x + α * d), ∇f(x + α * d) where f is the minimized function
• x₀::AbstractVector: the initial point
• d::AbstractVector: the search direction. Must be a descent direction, i.e. d⋅∇f(x₀) < 0
• y₀: (optional) the value of f(x₀) if it is known beforehand
• g₀: (optional) the value of ∇f(x₀) if it is known beforehand

Keywords

• α=1: the initial value of α
• αmax=Inf: the maximum allowed value of α
• β=1e-4: the coefficient in Wolfe conditions
• σ=0.5: the coefficient in Wolfe conditions

Return the maximum absolute values of diagonal and off-diagonal elements of A.