Library documentation

struct AndersonMixing{T <: Real} <: FixedPointAlgorithm
AndersonMixing(m::Int;
                  damping::Real = 1,
                  maxiter::Int=MAXITER[], # 1_000_000
                  gradtol::Real=GRADTOL[], # 1e-8
                  verbosity::Int=VERBOSITY[]) # 1

Anderson mixing, also known as Anderson acceleration, for fixed point problems.

Parameters

• m::Int: The number of previous iterates to use for Anderson extrapolation.
• damping::Real: The damping parameter for Anderson extrapolation; a value of 1 corresponds to no damping, while a value between 0 and 1 corresponds to under-relaxation.
• maxiter::Int: The maximum number of iterations.
• gradtol::T: The tolerance for the norm of the residual.
• verbosity::Int: The verbosity level of the optimization algorithm.

The verbosity level use the following scheme:

• 0: no output
• 1: only warnings upon non-convergence
• 2: convergence information at the end of the algorithm
• 3: progress information after each iteration

struct ConjugateGradient{F<:CGFlavor,T<:Real,L<:AbstractLineSearch} <: OptimizationAlgorithm
ConjugateGradient(;
                  flavor::CGFlavor=HagerZhang(),
                  restart::Int=typemax(Int);
                  maxiter::Int=MAXITER[], # 1_000_000
                  gradtol::Real=GRADTOL[], # 1e-8
                  verbosity::Int=VERBOSITY[], # 1
                  ls_maxiter::Int=LS_MAXITER[], # 10
                  ls_maxfg::Int=LS_MAXFG[], # 20
                  ls_verbosity::Int=LS_VERBOSITY[], # 1
                  linesearch = HagerZhangLineSearch(maxiter=ls_maxiter, maxfg=ls_maxfg, verbosity=ls_verbosity))

ConjugateGradient optimization algorithm.

Parameters

• flavor: The flavor of the conjugate gradient algorithm (for selecting the β parameter; see below)
• restart::Int: The number of iterations after which to reset the search direction.
• maxiter::Int: The maximum number of iterations.
• gradtol::T: The tolerance for the norm of the gradient.
• verbosity::Int: The verbosity level of the optimization algorithm.
• ls_maxiter::Int: The maximum number of iterations for the line search.
• ls_maxfg::Int: The maximum number of function evaluations for the line search.
• ls_verbosity::Int: The verbosity level of the line search algorithm.
• linesearch: The line search algorithm to use; if a custom value is provided, it overrides ls_maxiter, ls_maxfg, and ls_verbosity.

Both verbosity levels use the following scheme:

• 0: no output
• 1: only warnings upon non-convergence
• 2: convergence information at the end of the algorithm
• 3: progress information after each iteration
• 4: more detailed information (only for the linesearch)

The flavor parameter can take the values

• HagerZhang(; η::Real=4 // 10, θ::Real=1 // 1): Hager-Zhang formula for β
• HestenesStiefel(; pos = true): Hestenes-Stiefel formula for β
• FletcherReeves(): Fletcher-Reeves formula for β
• PolakRibiere(; pos = true): Polak-Ribiere formula for β
• DaiYuan(): Dai-Yuan formula for β

GradientDescent(; 
                maxiter::Int=MAXITER[], # 1_000_000
                gradtol::Real=GRADTOL[], # 1e-8
                verbosity::Int=VERBOSITY[], # 1
                ls_maxiter::Int=LS_MAXITER[], # 10
                ls_maxfg::Int=LS_MAXFG[], # 20
                ls_verbosity::Int=LS_VERBOSITY[], # 1
                linesearch = HagerZhangLineSearch(maxiter=ls_maxiter, maxfg=ls_maxfg, verbosity=ls_verbosity))

Gradient Descent optimization algorithm.

Parameters

• maxiter::Int: The maximum number of iterations.
• gradtol::T: The tolerance for the norm of the gradient.
• verbosity::Int: The verbosity level of the optimization algorithm.
• ls_maxiter::Int: The maximum number of iterations for the line search.
• ls_maxfg::Int: The maximum number of function evaluations for the line search.
• ls_verbosity::Int: The verbosity level of the line search algorithm.
• linesearch: The line search algorithm to use; if a custom value is provided, it overrides ls_maxiter, ls_maxfg, and ls_verbosity.

Both verbosity and ls_verbosity use the following scheme:

• 0: no output
• 1: only warnings upon non-convergence
• 2: convergence information at the end of the algorithm
• 3: progress information after each iteration
• 4: more detailed information (only for the linesearch)

(ls::HagerZhangLineSearch)(fg, x₀, η₀, fg₀ = fg(x₀);
                retract = _retract, inner = _inner,
                initialguess = one(fg₀[1]), acceptfirst = false,
                maxiter = ls.maxiter, maxfg = lsmaxfg, verbosity = ls.verbosity)

Perform a Hager-Zhang line search to find a step length that satisfies the (approximate) Wolfe conditions.

Arguments:

• ls::HagerZhangLineSearch: The HagerZhangLineSearch object.
• fg: Function that computes the objective function and its gradient.
• x₀: Starting point.
• η₀: Search direction.
• fg₀: Objective function and gradient evaluated at x₀. Defaults to fg(x₀), but can be supplied if this information has already been calculated.

Keyword Arguments:

• retract: Function that performs the retraction step, i.e. the generalisation of x₀ + α * η₀. Defaults to _retract.
• inner: Function that computes the inner product between search direction and gradient. Defaults to _inner.
• initialguess::Real: Initial guess for the step length. Defaults to one(fg₀[1]).
• acceptfirst::Bool: Parameter that controls whether the initial guess can be accepted if it satisfies the strong Wolfe conditions. Defaults to false, thus requiring at least one line search iteration and one extra function evaluation.
• maxiter::Int: Hard limit on the number of iterations. Default is 50.
• maxfg::Int: Soft limit on the number of function evaluations. Default is 100.
• verbosity::Int: The verbosity level (see below). Default is 0.

Verbosity Levels

• 0: No output.
• 1: Single output about convergence when the linesearch has terminated.
• 2: Output after the start and every individual iteration step of the Hager-Zhang linesearch.
• 3: Additional output about the initial bracketing and further bracket update and bisection steps.
• 4: Output after every function evaluation in the bracketing, updating, and bisection steps.

Returns:

• x: The point retract(x₀, η₀, α) where the (approximate) Wolfe conditions are satisfied.
• f: Function value at x.
• g: Gradient at x.
• ξ: Tangent at x to the line search path.
• α: Step length that satisfies the (approximate) Wolfe conditions.
• numfg: Number of function evaluations performed.

struct HagerZhangLineSearch{T<:Real} <: AbstractLineSearch
HagerZhangLineSearch(; c₁::Real = 1//10, c₂::Real = 9//10, ϵ::Real = 1//10^6,
                    θ::Real = 1//2, γ::Real = 2//3, ρ::Real = 5//1)

Constructs a Hager-Zhang line search object with the specified parameters.

Arguments:

• c₁::Real: Parameter for the (approximate) first Wolfe condition (Armijo rule), controlling sufficient decay of function value: c₁ < 1/2 < c₂. Default is 1//10.
• c₂::Real: Parameter for the second Wolfe condition (curvature contition), controlling sufficient decay of slope: c₁ < 1/2 < c₂. Default is 9//10.
• ϵ::Real: Parameter for expected accuracy of objective function, controlling maximal allowed increase in function value. Default is 1//10^6.
• θ::Real: Parameter regulating the bisection step. Default is 1//2 (should probably not be changed).
• γ::Real: Parameter triggering the bisection step, namely if bracket reduction rate is slower than γ. Default is 2//3.
• ρ::Real: Parameter controlling the initial bracket expansion rate. Default is 5//1.
• maxiter::Int: Hard limit on the number of iterations. Default is OptimKit.LS_MAXITER[] (set to 50).
• maxfg::Int: Soft limit on the number of function evaluations. Default is OptimKit.LS_MAXFG[] (set to 100).
• verbosity::Int: The verbosity level (see below). Default is OptimKit.LS_VERBOSITY[] (set to 0).

Returns:

This method returns a HagerZhangLineSearch object ls, that can then be can be applied as ls(fg, x₀, η₀; kwargs...) to perform a line search for function fg that computes the objective function and its gradient at a given point, starting from x₀ in direction η₀.

LBFGS(m::Int = 8; 
      acceptfirst::Bool = true,
      maxiter::Int=MAXITER[], # 1_000_000
      gradtol::Real=GRADTOL[], # 1e-8
      verbosity::Int=VERBOSITY[], # 1
      ls_maxiter::Int=LS_MAXITER[], # 10
      ls_maxfg::Int=LS_MAXFG[], # 20
      ls_verbosity::Int=LS_VERBOSITY[], # 1
      linesearch = HagerZhangLineSearch(maxiter=ls_maxiter, maxfg=ls_maxfg, verbosity=ls_verbosity))

LBFGS optimization algorithm.

Parameters

• m::Int: The number of previous iterations to store for the limited memory BFGS approximation.
• maxiter::Int: The maximum number of iterations.
• gradtol::T: The tolerance for the norm of the gradient.
• verbosity::Int: The verbosity level of the optimization algorithm.
• acceptfirst::Bool: Whether to accept the first step of the line search.
• ls_maxiter::Int: The maximum number of iterations for the line search.
• ls_maxfg::Int: The maximum number of function evaluations for the line search.
• ls_verbosity::Int: The verbosity level of the line search algorithm.
• linesearch: The line search algorithm to use; if a custom value is provided, it overrides ls_maxiter, ls_maxfg, and ls_verbosity.

Both verbosity and ls_verbosity use the following scheme:

• 0: no output
• 1: only warnings upon non-convergence
• 2: convergence information at the end of the algorithm
• 3: progress information after each iteration
• 4: more detailed information (only for the linesearch)

struct SimpleIteration{T <: Real} <: FixedPointAlgorithm
SimpleIteration(;
                maxiter::Int=MAXITER[], # 1_000_000
                gradtol::Real=GRADTOL[], # 1e-8
                verbosity::Int=VERBOSITY[]) # 1

Simple iteration for fixed point problems.

Parameters

• maxiter::Int: The maximum number of iterations.
• gradtol::Real: The tolerance for the norm of the residual.
• verbosity::Int: The verbosity level of the optimization algorithm.

The verbosity level use the following scheme:

• 0: no output
• 1: only warnings upon non-convergence
• 2: convergence information at the end of the algorithm
• 3: progress information after each iteration

fixedpoint(fp, x, alg;
              finalize! = _finalize!,
              shouldstop = DefaultShouldStop(alg.maxiter),
              hasconverged = DefaultHasConverged(alg.gradtol),
              retract = _retract, invretract = _invretract,
              inner = _inner, (transport!) = _transport!,
              (scale!) = _scale!, (add!) = _add!,
              isometrictransport = (transport! == _transport! && inner == _inner))
-> x, g, numfp, history

Find a fixed point of the function fp starting from an initial point x₀ and using the fixed point algorithm alg, which is an instance of SimpleIteration or AndersonMixing.

Returns the final point x, the residual g, the total number of calls to fp, and the history of the norm of the residual across the different iterations.

The algorithm is run until either hasconverged(x, false, g, normg) returns true or shouldstop(x, false, g, numfp, numiter, time) returns true. The latter case happening before the former is considered to be a failure to converge, and a warning is issued.

The keyword arguments are:

• finalize!::Function: A function that takes the final point x, a dummy variable f = false, the residual g, and the iteration number, and returns a possibly modified values for x, f and g. By default, the identity is used. It is the user's responsibility to ensure that the modified values do not lead to inconsistencies within the optimization algorithm.
• hasconverged::Function: A function that takes the current point x, a dummy variable f = false, the residual r, and the norm of the residual, and returns a boolean indicating whether the fixed point iteration has converged. By default, the norm of the residual is compared to the tolerance gradtol as encoded in the algorithm instance.
• shouldstop::Function: A function that takes the current point x, a dummy variable f = false, the residuals g, the number of calls to fg, the iteration number, and the time spent so far, and returns a boolean indicating whether the optimization should stop. By default, the number of iterations is compared to the maximum number of iterations as encoded in the algorithm instance.

Check the README of this package for further details on creating an algorithm instance, as well as for the meaning of the remaining keyword arguments and their default values.

Also see SimpleIteration and AndersonMixing.

optimize(fg, x, alg;
              precondition = _precondition,
              (finalize!) = _finalize!,
              hasconverged = DefaultHasConverged(alg.gradtol),
              shouldstop = DefaultShouldStop(alg.maxiter),
              retract = _retract,
              inner=_inner,
              transport! = _transport!,
              scale! =_scale!,
              add! = _add!,
              isometrictransport = (transport! == _transport! && inner == _inner))
-> x, f, g, numfg, history

Optimize (minimize) the objective function returned as the first value of fg, where the second value contains the gradient, starting from a point x and using the algorithm algorithm, which is an instance of GradientDescent, ConjugateGradient or LBFGS.

Returns the final point x, the coresponding function value f and gradient g, the total number of calls to fg, and the history of the gradient norm across the different iterations.

The algorithm is run until either hasconverged(x, f, g, norm(g)) returns true or shouldstop(x, f, g, numfg, numiter, time) returns true. The latter case happening before the former is considered to be a failure to converge, and a warning is issued.

The keyword arguments are:

• precondition::Function: A function that takes the current point x and the gradient g and returns a preconditioned gradient. By default, the identity is used.
• finalize!::Function: A function that takes the final point x, the function value f, the gradient g, and the iteration number, and returns a possibly modified values for x, f and g. By default, the identity is used. It is the user's responsibility to ensure that the modified values do not lead to inconsistencies within the optimization algorithm.
• hasconverged::Function: A function that takes the current point x, the function value f, the gradient g, and the norm of the gradient, and returns a boolean indicating whether the optimization has converged. By default, the norm of the gradient is compared to the tolerance gradtol as encoded in the algorithm instance.
• shouldstop::Function: A function that takes the current point x, the function value f, the gradient g, the number of calls to fg, the iteration number, and the time spent so far, and returns a boolean indicating whether the optimization should stop. By default, the number of iterations is compared to the maximum number of iterations as encoded in the algorithm instance.

Check the README of this package for further details on creating an algorithm instance, as well as for the meaning of the remaining keyword arguments and their default values.

Also see GradientDescent, ConjugateGradient, LBFGS.

optimtest(fg, x, [d]; alpha = -0.1:0.001:0.1, retract = _retract, inner = _inner)
-> αs, fs, dfs1, dfs2

Test the compatibility between the computation of the gradient, the retraction and the inner product by computing the derivative of the objective function along a curve corresponding to a retraction starting at the point x in the direction d in two different ways. In particular, at point αs which are in the middle of the points in the original range or list alpha, both the function value fs as well as the two different values for the derivative dfs1 and dfs2 are returned, where the derivatives are computed by

1. numerical differentation, i.e. dfs1 contains the values (fg(retract(x, d, alpha[i+1])[1])[1] - fg(retract(x, d, alpha[i])[1])[1])/(alpha[i+1]-alpha[i]) as an estimate for the derivative at the point (alpha[i]+alpha[i+1])/2
2. using the gradient, i.e. dfs2 contains the values inner(xα, dα, gα) where xα, dα = retract(x, d, α) for values α = (alpha[i]+alpha[i+1])/2 and gα = fg(xα)[2].

It is up to the user to check that the values in dfs1 and dfs2 match up to expected precision, by inspecting the numerical values or plotting them. If these values don't match, the linesearch in optimize cannot be expected to work.