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/Algorithmpairs, 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)
endFor 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:
initialize_stateconstructs an entirely new state for the algorithminitialize_state!(in-place) reset of an existing state.
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
endNote 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
endRunning 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.0Note 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.residuals5-element Vector{Float64}:
56.25
10.94831314878893
1.1119950267585779
0.018065294806394405
5.093543919088006e-6Here 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
endSince 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.0Note 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.
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).
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).
AlgorithmsInterface.solve! — Method
solve!(problem::Problem, algorithm::Algorithm, state::State; kwargs...)Solve the Problem using an Algorithm, starting from a given State. The state is modified in-place.
All keyword arguments are passed to the initialize_state!(problem, algorithm, state) function.
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!.
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:
- Checking for convergence with
is_finished! - Incrementing the state
increment! - Performing a step
step! - Repeat
AlgorithmsInterface.step! — Method
step!(problem::Problem, algorithm::Algorithm, state::State)Perform the current step of an Algorithm solving a Problem modifying the algorithm's State.
Algorithm
AlgorithmsInterface.Algorithm — Type
AlgorithmAn 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.
Problem
AlgorithmsInterface.Problem — Type
ProblemAn 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
costfunction $f: C → ℝ$ - a gradient function $\operatorname{grad}f$
The problem could specify these in four different forms:
- a function
c = cost(x)and a gradientd = gradient(x) - a function
c = cost(x)and an in-place gradientgradient!(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.
State
AlgorithmsInterface.State — Type
StateAn 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– aStoppingCriterionStatethat indicates whether anAlgorithmwill stop after this iteration or has stopped.iterate– the current iterate $x^{(k)}$.
Methods
The following methods should be implemented for a state
increment!(state)
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.
AlgorithmsInterface.DefaultState — Type
DefaultState <: StateA 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
iteratestores the current iterate $x^{(k)}$.stopping_criterion_statestores theStoppingCriterionStatebelonging to theStoppingCriterionof theAlgorithm.datastores any further data, for example as aNamedTuple, ornothingif not needed.iteration::Intstores 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.
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.