GitHub

The algorithm interface

General design ideas

The interface this package provides is based on three ingredients of running an algorithm consists of:

  • a Problem that is to be solved and contains all information that is algorithm independent. This is static information in the sense that it does not change during the runtime of the algorithm.
  • an Algorithm that includes all of the settings and parameters that an algorithm. this is also information that is static.
  • a State that contains all remaining data, especially data that might vary during the iteration, temporary caches, for example the current iteration the algorithm run is in and the current iterate, respectively.

The combination of the static information should be enough to initialize the varying data.

This general scheme is a guiding principle of the package, splitting information into static or configuration types or data that allows to initialize_state a corresponding variable data type.

The order of arguments is given by two ideas

  1. for non-mutating functions the order should be from the most fixed data to the most variable one.

For example the three types just mentioned would be ordered like f(problem, algorithm, state)

  1. For mutating functions the variable that is mutated comes first, for the remainder the guiding principle from 1 continues.

The main case here is f!(state, problem, algorithm).

AlgorithmsInterface.initialize_state! — Method
state = initialize_state(problem::Problem, algorithm::Algorithm; kwargs...)
state = initialize_state!(state::State, problem::Problem, algorithm::Algorithm; 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.

source
AlgorithmsInterface.initialize_state — Method
state = initialize_state(problem::Problem, algorithm::Algorithm; kwargs...)
state = initialize_state!(state::State, problem::Problem, algorithm::Algorithm; 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.

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

Algorithm

AlgorithmsInterface.Algorithm — Type
Algorithm

An abstract type to represent an algorithm.

A concrete algorithm contains all static parameters that characterise the algorithms. 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 then could that these are given 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 is currently 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 a State either is currently performing or was last performed

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

source