Stopping criteria

Stopping criteria are implemented as a functor and inherit from the base type

Manopt.StoppingCriterionType
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).

source

They can also be grouped, which is summarized in the type of a set of criteria

Manopt.StoppingCriterionSetType
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.

source

The stopping criteria s might have certain internal values/fields it uses to verify against. This is done when calling them as a function s(amp::AbstractManoptProblem, ams::AbstractManoptSolverState), where the AbstractManoptProblem and the AbstractManoptSolverState together represent the current state of the solver. The functor returns either false when the stopping criterion is not fulfilled or true otherwise. One field all criteria should have is the s.reason, a string giving the reason to stop, see get_reason.

Generic stopping criteria

The following generic stopping criteria are available. Some require that, for example, the corresponding AbstractManoptSolverState have a field gradient when the criterion should access that.

Further stopping criteria might be available for individual solvers.

Manopt.StopAfterType
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).

Constructor

StopAfter(t)

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

source
Manopt.StopAfterIterationType
StopAfterIteration <: StoppingCriterion

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

Fields

  • maxIter stores the maximal iteration number where to stop at
  • reason stores a reason of stopping if the stopping criterion has one be reached, see get_reason.

Constructor

StopAfterIteration(maxIter)

initialize the functor to indicate to stop after maxIter iterations.

source
Manopt.StopWhenAllType
StopWhenAll <: StoppingCriterion

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,...)
source
Manopt.StopWhenAnyType
StopWhenAny <: StoppingCriterion

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...)
source
Manopt.StopWhenChangeLessType
StopWhenChangeLess <: StoppingCriterion

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

StopWhenChangeLess(
    M::AbstractManifold,
    ε::Float64;
    storage::StoreStateAction=StoreStateAction([:Iterate]),
    inverse_retraction_method::IRT=default_inverse_retraction_method(manifold)
)

initialize the stopping criterion to a threshold ε using the StoreStateActiona, 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.

source
Manopt.StopWhenCostLessType
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 ε.

source
Manopt.StopWhenCostNaNType
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.

source
Manopt.StopWhenEntryChangeLessType
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

  • reason: store a string reason when the stop was indicated
  • 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]),
)
source
Manopt.StopWhenGradientChangeLessType
StopWhenGradientChangeLess <: StoppingCriterion

A stopping criterion based on the change of the gradient

\lVert \mathcal T_{p^{(k)}\gets p^{(k-1)} \operatorname{grad} f(p^{(k-1)}) -  \operatorname{grad} f(p^{(k-1)}) \rVert < ε

Constructor

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

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.

source
Manopt.StopWhenGradientNormLessType
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`
  • threshold: the threshold to indicate to stop when the distance is below this value

Internal fields

  • reason: store a string reason when the stop was indicated
  • at_iteration: store the iteration at which the stop indication happened

Constructor

StopWhenGradientNormLess(ε; norm=(M,p,X) -> norm(M,p,X))

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.

source
Manopt.StopWhenIterateNaNType
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.

source
Manopt.StopWhenSmallerOrEqualType
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
  • reason stores a reason of stopping if the stopping criterion has one be reached, see get_reason.

Constructor

StopWhenSmallerOrEqual(value, minValue)

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

source
Manopt.StopWhenStepsizeLessType
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 ε.

source
Manopt.StopWhenSubgradientNormLessType
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 ε.

source

Functions for stopping criteria

There are a few functions to update, combine, and modify stopping criteria, especially to update internal values even for stopping criteria already being used within an AbstractManoptSolverState structure.

Base.:&Method
&(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(1e-6)
b = a & StopWhenGradientNormLess(1e-6)

Is the same as

a = StopWhenAll(StopAfterIteration(200), StopWhenChangeLess(1e-6))
b = StopWhenAll(StopAfterIteration(200), StopWhenChangeLess(1e-6), StopWhenGradientNormLess(1e-6))
source
Base.:|Method
|(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(1e-6)
b = a | StopWhenGradientNormLess(1e-6)

Is the same as

a = StopWhenAny(StopAfterIteration(200), StopWhenChangeLess(1e-6))
b = StopWhenAny(StopAfterIteration(200), StopWhenChangeLess(1e-6), StopWhenGradientNormLess(1e-6))
source
Manopt.get_active_stopping_criteriaMethod
get_active_stopping_criteria(c)

returns all active stopping criteria, if any, that are within a StoppingCriterionc, 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.

source
Manopt.indicates_convergenceMethod
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.
source
Manopt.update_stopping_criterion!Method
update_stopping_criterion!(c::Stoppingcriterion, s::Symbol, v::value)
update_stopping_criterion!(s::AbstractManoptSolverState, symbol::Symbol, v::value)
update_stopping_criterion!(c::Stoppingcriterion, ::Val{Symbol}, v::value)

Update a value within a stopping criterion, specified by the symbol s, to v. If a criterion does not have a value assigned that corresponds to s, the update is ignored.

For the second signature, the stopping criterion within the AbstractManoptSolverStateo is updated.

To see which symbol updates which value, see the specific stopping criteria. They should use dispatch per symbol value (the third signature).

source
Manopt.update_stopping_criterion!Method
update_stopping_criterion!(c::StopWhenSubgradientNormLess, :MinSubgradNorm, v::Float64)

Update the minimal subgradient norm when an algorithm shall stop

source