Stopping criteria

StoppingCriterion

An abstract type for the functors representing stopping criteria, so they are callable structures. The naming Scheme follows functions, see for example StopAfterIteration.

Every StoppingCriterion has to provide a constructor and its function has to have the interface (p,o,i) where a AbstractManoptProblem as well as AbstractManoptSolverState and the current number of iterations are the arguments and returns a boolean whether to stop or not.

By default each StoppingCriterion should provide a fields reason to provide details when a criterion is met (and that is empty otherwise).

StoppingCriterionGroup <: StoppingCriterion

An abstract type for a Stopping Criterion that itself consists of a set of Stopping criteria. In total it acts as a stopping criterion itself. Examples are StopWhenAny and StopWhenAll that can be used to combine stopping criteria.

StopAfter <: StoppingCriterion

store a threshold when to stop looking at the complete runtime. It uses time_ns() to measure the time and you provide a Period as a time limit, for example Minute(15).

Fields

• threshold stores the Period after which to stop
• start stores the starting time when the algorithm is started, that is a call with i=0.
• time stores the elapsed time
• at_iteration indicates at which iteration (including i=0) the stopping criterion was fulfilled and is -1 while it is not fulfilled.

Constructor

StopAfter(t)

initialize the stopping criterion to a Period t to stop after.

StopAfterIteration <: StoppingCriterion

A functor for a stopping criterion to stop after a maximal number of iterations.

Fields

• max_iterations stores the maximal iteration number where to stop at
• at_iteration indicates at which iteration (including i=0) the stopping criterion was fulfilled and is -1 while it is not fulfilled.

Constructor

StopAfterIteration(maxIter)

initialize the functor to indicate to stop after maxIter iterations.

StopWhenAll <: StoppingCriterionSet

store an array of StoppingCriterion elements and indicates to stop, when all indicate to stop. The reason is given by the concatenation of all reasons.

Constructor

StopWhenAll(c::NTuple{N,StoppingCriterion} where N)
StopWhenAll(c::StoppingCriterion,...)

StopWhenAny <: StoppingCriterionSet

store an array of StoppingCriterion elements and indicates to stop, when any single one indicates to stop. The reason is given by the concatenation of all reasons (assuming that all non-indicating return "").

Constructor

StopWhenAny(c::NTuple{N,StoppingCriterion} where N)
StopWhenAny(c::StoppingCriterion...)

StopWhenChangeLess <: StoppingCriterion

stores a threshold when to stop looking at the norm of the change of the optimization variable from within a AbstractManoptSolverState s. That ism by accessing get_iterate(s) and comparing successive iterates. For the storage a StoreStateAction is used.

Fields

• at_iteration::Int: an integer indicating at which the stopping criterion last indicted to stop, which might also be before the solver started (0). Any negative value indicates that this was not yet the case;
• last_change::Real: the last change recorded in this stopping criterion
• inverse_retraction_method::AbstractInverseRetractionMethod: an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• storage::StoreStateAction: a storage to access the previous iterate
• at_iteration::Int: indicate at which iteration this stopping criterion was last active.
• inverse_retraction: An AbstractInverseRetractionMethod that can be passed to approximate the distance by this inverse retraction and a norm on the tangent space. This can be used if neither the distance nor the logarithmic map are availannle on M.
• last_change: store the last change
• storage: A StoreStateAction to access the previous iterate.
• threshold: the threshold for the change to check (run under to stop)
• outer_norm: if M is a manifold with components, this can be used to specify the norm, that is used to compute the overall distance based on the element-wise distance. You can deactivate this, but setting this value to missing.

Example

On an AbstractPowerManifold like $\mathcal M = \mathcal N^n$ any point $p = (p_1,…,p_n) ∈ \mathcal M$ is a vector of length $n$ with of points $p_i ∈ \mathcal N$. Then, denoting the outer_norm by $r$, the distance of two points $p,q ∈ \mathcal M$ is given by

\mathrm{d}(p,q) = \Bigl( \sum_{k=1}^n \mathrm{d}(p_k,q_k)^r \Bigr)^{\frac{1}{r}},

where the sum turns into a maximum for the case $r=∞$. The outer_norm has no effect on manifolds that do not consist of components.

If the manifold does not have components, the outer norm is ignored.

Constructor

StopWhenChangeLess(
    M::AbstractManifold,
    threshold::Float64;
    storage::StoreStateAction=StoreStateAction([:Iterate]),
    inverse_retraction_method::IRT=default_inverse_retraction_method(M)
    outer_norm::Union{Missing,Real}=missing
)

initialize the stopping criterion to a threshold ε using the StoreStateAction a, which is initialized to just store :Iterate by default. You can also provide an inverseretractionmethod for the distance or a manifold to use its default inverse retraction.

StopWhenCostLess <: StoppingCriterion

store a threshold when to stop looking at the cost function of the optimization problem from within a AbstractManoptProblem, i.e get_cost(p,get_iterate(o)).

Constructor

StopWhenCostLess(ε)

initialize the stopping criterion to a threshold ε.

StopWhenCostNaN <: StoppingCriterion

stop looking at the cost function of the optimization problem from within a AbstractManoptProblem, i.e get_cost(p,get_iterate(o)).

Constructor

StopWhenCostNaN()

initialize the stopping criterion to NaN.

StopWhenEntryChangeLess

Evaluate whether a certain fields change is less than a certain threshold

Fields

• field: a symbol addressing the corresponding field in a certain subtype of AbstractManoptSolverState to track
• distance: a function (problem, state, v1, v2) -> R that computes the distance between two possible values of the field
• storage: a StoreStateAction to store the previous value of the field
• threshold: the threshold to indicate to stop when the distance is below this value

Internal fields

• at_iteration: store the iteration at which the stop indication happened

stores a threshold when to stop looking at the norm of the change of the optimization variable from within a AbstractManoptSolverState, i.e get_iterate(o). For the storage a StoreStateAction is used

Constructor

StopWhenEntryChangeLess(
    field::Symbol
    distance,
    threshold;
    storage::StoreStateAction=StoreStateAction([field]),
)

StopWhenGradientChangeLess <: StoppingCriterion

A stopping criterion based on the change of the gradient.

Fields

• at_iteration::Int: an integer indicating at which the stopping criterion last indicted to stop, which might also be before the solver started (0). Any negative value indicates that this was not yet the case;
• last_change::Real: the last change recorded in this stopping criterion
• vector_transport_method::AbstractVectorTransportMethodP: a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• storage::StoreStateAction: a storage to access the previous iterate
• threshold: the threshold for the change to check (run under to stop)
• outer_norm: if M is a manifold with components, this can be used to specify the norm, that is used to compute the overall distance based on the element-wise distance. You can deactivate this, but setting this value to missing.

Example

On an AbstractPowerManifold like $\mathcal M = \mathcal N^n$ any point $p = (p_1,…,p_n) ∈ \mathcal M$ is a vector of length $n$ with of points $p_i ∈ \mathcal N$. Then, denoting the outer_norm by $r$, the norm of the difference of tangent vectors like the last and current gradien $X,Y ∈ \mathcal M$ is given by

\lVert X-Y \rVert_{p} = \Bigl( \sum_{k=1}^n \lVert X_k-Y_k \rVert_{p_k}^r \Bigr)^{\frac{1}{r}},

where the sum turns into a maximum for the case $r=∞$. The outer_norm has no effect on manifols, that do not consist of components.

Constructor

StopWhenGradientChangeLess(
    M::AbstractManifold,
    ε::Float64;
    storage::StoreStateAction=StoreStateAction([:Iterate]),
    vector_transport_method::IRT=default_vector_transport_method(M),
    outer_norm::N=missing
)

Create a stopping criterion with threshold ε for the change gradient, that is, this criterion indicates to stop when get_gradient is in (norm of) its change less than ε, where vector_transport_method denotes the vector transport $\mathcal T$ used.

StopWhenGradientNormLess <: StoppingCriterion

A stopping criterion based on the current gradient norm.

Fields

• norm: a function (M::AbstractManifold, p, X) -> ℝ that computes a norm of the gradient X in the tangent space at p on M. For manifolds with components provide(M::AbstractManifold, p, X, r) -> ℝ`.
• threshold: the threshold to indicate to stop when the distance is below this value
• outer_norm: if M is a manifold with components, this can be used to specify the norm, that is used to compute the overall distance based on the element-wise distance.

Internal fields

• last_change store the last change
• at_iteration store the iteration at which the stop indication happened

Example

On an AbstractPowerManifold like $\mathcal M = \mathcal N^n$ any point $p = (p_1,…,p_n) ∈ \mathcal M$ is a vector of length $n$ with of points $p_i ∈ \mathcal N$. Then, denoting the outer_norm by $r$, the norm of a tangent vector like the current gradient $X ∈ \mathcal M$ is given by

\lVert X \rVert_{p} = \Bigl( \sum_{k=1}^n \lVert X_k \rVert_{p_k}^r \Bigr)^{\frac{1}{r}},

where the sum turns into a maximum for the case $r=∞$. The outer_norm has no effect on manifolds that do not consist of components.

If you pass in your individual norm, this can be deactivated on such manifolds by passing missing to outer_norm.

Constructor

StopWhenGradientNormLess(ε; norm=ManifoldsBase.norm, outer_norm=missing)

Create a stopping criterion with threshold ε for the gradient, that is, this criterion indicates to stop when get_gradient returns a gradient vector of norm less than ε, where the norm to use can be specified in the norm= keyword.

StopWhenIterateNaN <: StoppingCriterion

stop looking at the cost function of the optimization problem from within a AbstractManoptProblem, i.e get_cost(p,get_iterate(o)).

Constructor

StopWhenIterateNaN()

initialize the stopping criterion to NaN.

StopWhenSmallerOrEqual <: StoppingCriterion

A functor for an stopping criterion, where the algorithm if stopped when a variable is smaller than or equal to its minimum value.

Fields

• value stores the variable which has to fall under a threshold for the algorithm to stop
• minValue stores the threshold where, if the value is smaller or equal to this threshold, the algorithm stops

Constructor

StopWhenSmallerOrEqual(value, minValue)

initialize the functor to indicate to stop after value is smaller than or equal to minValue.

StopWhenStepsizeLess <: StoppingCriterion

stores a threshold when to stop looking at the last step size determined or found during the last iteration from within a AbstractManoptSolverState.

Constructor

StopWhenStepsizeLess(ε)

initialize the stopping criterion to a threshold ε.

StopWhenSubgradientNormLess <: StoppingCriterion

A stopping criterion based on the current subgradient norm.

Constructor

StopWhenSubgradientNormLess(ε::Float64)

Create a stopping criterion with threshold ε for the subgradient, that is, this criterion indicates to stop when get_subgradient returns a subgradient vector of norm less than ε.

&(s1,s2)
s1 & s2

Combine two StoppingCriterion within an StopWhenAll. If either s1 (or s2) is already an StopWhenAll, then s2 (or s1) is appended to the list of StoppingCriterion within s1 (or s2).

Example

a = StopAfterIteration(200) & StopWhenChangeLess(M, 1e-6)
b = a & StopWhenGradientNormLess(1e-6)

Is the same as

a = StopWhenAll(StopAfterIteration(200), StopWhenChangeLess(M, 1e-6))
b = StopWhenAll(StopAfterIteration(200), StopWhenChangeLess(M, 1e-6), StopWhenGradientNormLess(1e-6))

|(s1,s2)
s1 | s2

Combine two StoppingCriterion within an StopWhenAny. If either s1 (or s2) is already an StopWhenAny, then s2 (or s1) is appended to the list of StoppingCriterion within s1 (or s2)

Example

a = StopAfterIteration(200) | StopWhenChangeLess(M, 1e-6)
b = a | StopWhenGradientNormLess(1e-6)

Is the same as

a = StopWhenAny(StopAfterIteration(200), StopWhenChangeLess(M, 1e-6))
b = StopWhenAny(StopAfterIteration(200), StopWhenChangeLess(M, 1e-6), StopWhenGradientNormLess(1e-6))

get_active_stopping_criteria(c)

returns all active stopping criteria, if any, that are within a StoppingCriterion c, and indicated a stop, that is their reason is nonempty. To be precise for a simple stopping criterion, this returns either an empty array if no stop is indicated or the stopping criterion as the only element of an array. For a StoppingCriterionSet all internal (even nested) criteria that indicate to stop are returned.

get_reason(s::AbstractManoptSolverState)

return the current reason stored within the StoppingCriterion from within the AbstractManoptSolverState. This reason is empty ("") if the criterion has never been met.

get_stopping_criteria(c)

return the array of internally stored StoppingCriterions for a StoppingCriterionSet c.

indicates_convergence(c::StoppingCriterion)

Return whether (true) or not (false) a StoppingCriterion does always mean that, when it indicates to stop, the solver has converged to a minimizer or critical point.

Note that this is independent of the actual state of the stopping criterion, whether some of them indicate to stop, but a purely type-based, static decision.

Examples

With s1=StopAfterIteration(20) and s2=StopWhenGradientNormLess(1e-7) the indicator yields

• indicates_convergence(s1) is false
• indicates_convergence(s2) is true
• indicates_convergence(s1 | s2) is false, since this might also stop after 20 iterations
• indicates_convergence(s1 & s2) is true, since s2 is fulfilled if this stops.

set_parameter!(c::StopAfter, :MaxTime, v::Period)

Update the time period after which an algorithm shall stop.

set_parameter!(c::StopAfterIteration, :;MaxIteration, v::Int)

Update the number of iterations after which the algorithm should stop.

set_parameter!(c::StopWhenChangeLess, :MinIterateChange, v::Int)

Update the minimal change below which an algorithm shall stop.

set_parameter!(c::StopWhenCostLess, :MinCost, v)

Update the minimal cost below which the algorithm shall stop

set_parameter!(c::StopWhenEntryChangeLess, :Threshold, v)

Update the minimal cost below which the algorithm shall stop

set_parameter!(c::StopWhenGradientChangeLess, :MinGradientChange, v)

Update the minimal change below which an algorithm shall stop.

set_parameter!(c::StopWhenGradientNormLess, :MinGradNorm, v::Float64)

Update the minimal gradient norm when an algorithm shall stop

set_parameter!(c::StopWhenStepsizeLess, :MinStepsize, v)

Update the minimal step size below which the algorithm shall stop

set_parameter!(c::StopWhenSubgradientNormLess, :MinSubgradNorm, v::Float64)

Update the minimal subgradient norm when an algorithm shall stop