The algorithm interface

This section starts a single, cohesive story that will weave through all documentation pages. We will incrementally build an iterative algorithm, enrich it with stopping criteria, and finally refine how it records (logs) its progress. Instead of presenting the API in the abstract, we anchor every concept in one concrete, tiny example you can copy & adapt.

Why an “interface” for algorithms? Iterative numerical methods nearly always share the same moving pieces:

  • immutable input (the mathematical problem you are solving),
  • immutable configuration (parameters and knobs of the chosen algorithm), and
  • mutable working data (current iterate, caches, diagnostics) that evolves as you step.

Bundling these together loosely without forcing one giant monolithic type makes it easier to:

  • reason about what is allowed to change and what must remain fixed,
  • write generic tooling (e.g. stopping logic, logging, benchmarking) that applies across many algorithms,
  • test algorithms in isolation by constructing minimal Problem/Algorithm pairs, and
  • extend behavior (add new stopping criteria, new logging events) without rewriting core loops.

The interface in this package formalizes those roles with three abstract types:

  • Problem: immutable, algorithm‑agnostic input data.
  • Algorithm: immutable configuration and parameters deciding how to iterate.
  • State: mutable data that evolves (current iterate, caches, counters, diagnostics).

It provides a framework for decomposing iterative methods into small, composable parts: concrete Problem/Algorithm/State types have to implement a minimal set of core functionality, and this package helps to stitch everything together and provide additional helper functionality such as stopping criteria and logging functionality.

Concrete example: Heron's method

To make everything tangible, we will work through a concrete example to illustrate the library's goals and concepts. Our running example is Heron's / Babylonian method for estimating $\sqrt{S}$. (see also the concise background on Wikipedia: Babylonian method (Heron's method)): Starting from an initial guess $x_0$, we may converge to the solution by iterating:

\[x_{k+1} = \frac{1}{2}\left(x_k + \frac{S}{x_k}\right)\]

We therefore suggest the following concrete implementations of the abstract types provided by this package: They are illustrative; various performance and generality questions will be left unaddressed to keep this example simple.

Algorithm types

using AlgorithmsInterface

struct SqrtProblem <: Problem
    S::Float64                # number whose square root we seek
end

struct HeronAlgorithm <: Algorithm
    stopping_criterion        # will be plugged in later (any StoppingCriterion)
end

For the state, we use the DefaultState, which stores the iterate, the iteration count and the stopping_criterion_state. If you need more, see defining your own state below.

Initialization

There are two main entry points provided by the interface:

Both have default implementations that work with a DefaultState, so there is nothing to define here.

Iteration steps

Algorithms define a mutable step via step!. For Heron's method:

function AlgorithmsInterface.step!(problem::SqrtProblem, algorithm::HeronAlgorithm, state::DefaultState)
    S = problem.S
    x = state.iterate
    state.iterate = 0.5 * (x + S / x)
    return state
end

Note that we are only focussing on the actual algorithm, and not incrementing the iteration counter. These kinds of bookkeeping should be handled by the AlgorithmsInterface.increment! function, which will by default already increment the iteration counter. The following generic functionality is therefore enough for our purposes, and does not need to be defined. Nevertheless, if additional bookkeeping would be desired, this can be achieved by overloading that function:

function AlgorithmsInterface.increment!(state::State)
    state.iteration += 1
    return state
end

Running the algorithm

With these definitions in place you can already run (assuming you also choose a stopping criterion – added in the next section):

function heron_sqrt(x; maxiter = 10)
    prob = SqrtProblem(x)
    alg  = HeronAlgorithm(StopAfterIteration(maxiter))
    return solve(prob, alg; iterate = 1.0)  # initial guess, allocates & runs
end

println("Approximate sqrt: ", heron_sqrt(16.0))
Approximate sqrt: 4.0

Note that solve will default to returning state.iterate. If desired, this can be customized by altering finalize_state!. We will refine this example with better halting logic and logging shortly.

Carrying extra data

Any additional data the algorithm needs can be stored in the data::D field of the DefaultState{V, S, D}.

struct TrackingHeronAlgorithm <: Algorithm
    stopping_criterion
end

function AlgorithmsInterface.step!(problem::SqrtProblem, ::TrackingHeronAlgorithm, state::DefaultState)
    S = problem.S
    x = state.iterate
    state.iterate = 0.5 * (x + S / x)
    push!(state.data.residuals, abs(state.iterate^2 - S))
    return state
end

problem = SqrtProblem(16.0)
tracking = TrackingHeronAlgorithm(StopAfterIteration(5))
state = initialize_state(problem, tracking, 1.0, (; residuals = Float64[]))
solve!(problem, tracking, state)
state.data.residuals
5-element Vector{Float64}:
 56.25
 10.94831314878893
  1.1119950267585779
  0.018065294806394405
  5.093543919088006e-6

Here the initial iterate and the data are passed positionally, as initialize_state(problem, algorithm, iterate, state_data).

Defining your own state

If you need named fields or want to dispatch on the state, subtype State instead. Such a state has to provide the same three properties, as well as its own initialization methods:

mutable struct HeronState <: State
    iterate::Float64          # current iterate
    iteration::Int            # current iteration count
    stopping_criterion_state  # any StoppingCriterionState
end

function AlgorithmsInterface.initialize_state(problem::SqrtProblem, algorithm::HeronAlgorithm; kwargs...)
    x0 = rand() # random initial guess
    stopping_criterion_state = initialize_state(problem, algorithm, algorithm.stopping_criterion)
    return HeronState(x0, 0, stopping_criterion_state)
end

function AlgorithmsInterface.initialize_state!(problem::SqrtProblem, algorithm::HeronAlgorithm, state::HeronState; kwargs...)
    # reset the state for the algorithm
    state.iterate = rand()
    state.iteration = 0

    # reset the state for the stopping criterion
    AlgorithmsInterface.initialize_state!(
        problem, algorithm, algorithm.stopping_criterion, state.stopping_criterion_state
    )
    return state
end

function AlgorithmsInterface.step!(problem::SqrtProblem, algorithm::HeronAlgorithm, state::HeronState)
    S = problem.S
    x = state.iterate
    state.iterate = 0.5 * (x + S / x)
    return state
end

Since this state picks its own initial guess, the iterate keyword is no longer needed:

println("Approximate sqrt: ", solve(SqrtProblem(16.0), HeronAlgorithm(StopAfterIteration(10))))
Approximate sqrt: 4.0

Note that the three required properties do not enforce a struct with these fields, and the properties can be emulated with correct implementations of Base.getproperty.

Reference: Core interface types & functions

Below are the automatic API docs for the core interface pieces. Read them after grasping the example above – the intent should now be clearer.

AlgorithmsInterface.finalize_state! — Method
output = finalize_state!(problem::Problem, algorithm::Algorithm, state::State)

Finalize the solver and decide what values get returned from the solve! call. By default, this is a no-op and returns the state.iterate, but this allows for further customization in other cases, for example to clean up used resources or output other data.

source
AlgorithmsInterface.initialize_state! — Method
state = initialize_state(problem::Problem, algorithm::Algorithm; kwargs...)
state = initialize_state!(problem::Problem, algorithm::Algorithm, state::State; kwargs...)

Initialize a State based on a Problem and an Algorithm. The kwargs... should allow to initialize for example the initial point. This can be done in-place for state, then only values that did change have to be provided.

By default, both work with a DefaultState, and also accept positional arguments:

state = initialize_state(problem, algorithm, iterate, state_data; kwargs...)
state = initialize_state!(problem, algorithm, state, iterate, state_data; kwargs...)

Here state_data is stored in the data field, and defaults to nothing when allocating and to state.data when resetting. The remaining kwargs... are passed on to the initialization of the StoppingCriterion.

Custom states should implement the keyword form, to avoid ambiguities with initialize_state(problem, algorithm, stopping_criterion).

source
AlgorithmsInterface.initialize_state — Method
state = initialize_state(problem::Problem, algorithm::Algorithm; kwargs...)
state = initialize_state!(problem::Problem, algorithm::Algorithm, state::State; kwargs...)

Initialize a State based on a Problem and an Algorithm. The kwargs... should allow to initialize for example the initial point. This can be done in-place for state, then only values that did change have to be provided.

By default, both work with a DefaultState, and also accept positional arguments:

state = initialize_state(problem, algorithm, iterate, state_data; kwargs...)
state = initialize_state!(problem, algorithm, state, iterate, state_data; kwargs...)

Here state_data is stored in the data field, and defaults to nothing when allocating and to state.data when resetting. The remaining kwargs... are passed on to the initialization of the StoppingCriterion.

Custom states should implement the keyword form, to avoid ambiguities with initialize_state(problem, algorithm, stopping_criterion).

source
AlgorithmsInterface.solve — Method
solve(problem::Problem, algorithm::Algorithm; kwargs...)

Solve the Problem using an Algorithm. The keyword arguments kwargs... have to provide enough details such that the corresponding state initialisation initialize_state(problem, algorithm) returns a state.

By default this method continues to call solve!.

source
AlgorithmsInterface.solve_loop! — Method
solve_loop!(problem::Problem, algorithm::Algorithm, state::State)

Provide the main loop of the iterative algorithm for a given problem and starting state.

This loop consists of:

  1. Checking for convergence with is_finished!
  2. Incrementing the state increment!
  3. Performing a step step!
  4. Repeat
source

Algorithm

AlgorithmsInterface.Algorithm — Type
Algorithm

An abstract type to represent an algorithm.

A concrete algorithm contains all static parameters that characterise the algorithm. Together with a Problem an Algorithm subtype should be able to initialize or reset a State.

Properties

Algorithms can contain any number of properties that are needed to define the algorithm, but should additionally contain the following properties to interact with the stopping criteria.

  • stopping_criterion::StoppingCriterion

Example

For a gradient descent algorithm the algorithm would specify which step size selection to use.

source

Problem

AlgorithmsInterface.Problem — Type
Problem

An abstract type to represent a problem to be solved with all its static properties, that do not change during an algorithm run.

Example

For a gradient descent algorithm the problem consists of

  • a cost function $f: C → ℝ$
  • a gradient function $\operatorname{grad}f$

The problem could specify these in four different forms:

  • a function c = cost(x) and a gradient d = gradient(x)
  • a function c = cost(x) and an in-place gradient gradient!(d,x)
  • a combined cost-grad function (c,d) = costgrad(x)
  • a combined cost-grad function (c, d) = costgrad!(d, x) that computes the gradient in-place.
source

State

AlgorithmsInterface.State — Type
State

An abstract type to represent the state an iterative algorithm is in.

The state consists of any information that describes the current step the algorithm is in and keeps all information needed from one step to the next.

Properties

In order to interact with the stopping criteria, the state should contain the following properties, and provide corresponding getproperty and setproperty! methods.

  • iteration – the current iteration step $k$ that is currently being performed or was last performed.
  • stopping_criterion_state – a StoppingCriterionState that indicates whether an Algorithm will stop after this iteration or has stopped.
  • iterate – the current iterate $x^{(k)}$.

Methods

The following methods should be implemented for a state

source
AlgorithmsInterface.increment! — Method
increment!(state::State)

Increment the current iteration that a State is currently performing or was last performing.

The default assumes that the current iteration is stored in state.iteration.

source
AlgorithmsInterface.DefaultState — Type
DefaultState <: State

A State that stores the required properties for the State interface, together with a data field for any further data an Algorithm needs. It is the state used by the default initialize_state and initialize_state!.

For more involved states, consider defining your own subtype of State instead.

Fields

  • iterate stores the current iterate $x^{(k)}$.
  • stopping_criterion_state stores the StoppingCriterionState belonging to the StoppingCriterion of the Algorithm.
  • data stores any further data, for example as a NamedTuple, or nothing if not needed.
  • iteration::Int stores the current iteration step $k$ that is currently being performed or was last performed.

Constructor

DefaultState(iterate, stopping_criterion_state, data = nothing)

Initialize the state to start at iterate with iteration 0.

source

Next: Stopping criteria

Proceed to the stopping criteria section to add robust halting logic (iteration caps, time limits, tolerance on successive iterates, and combinations) to this square‑root example.