GitHub

The Stopping Criterion

Manopt.StoppingCriterion — Type
StoppingCriterion <: AbstractManifoldFunction

An abstract type for the functions 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 (amp, ams, k) where an AbstractManoptProblem amp as well as an AbstractManoptSolverState ams and the current iteration k are the arguments. The function always returns a boolean indicating whether to stop or not.

By default each StoppingCriterion should provide a field at_iteration to provide the iteration it (last) indicated to stop. Further fields should provide enough information, such that a human-readable reason can be assembled, see get_reason.

source

The stopping criterion is a function (problem, state, k) -> Bool that after the initialization and every iteration determines whether a solver should stop. It is passed to a solver via the stopping_criterion= keyword in the high-level interfaces. Since the criterion is stored in the solver state, state constructors also accept that keyword.

A stopping criterion should usually store the iteration number at which it last indicated to stop. Within Manopt.jl this is the field at_iteration. It should reset its internal variables when called with k=0, that is upon initialization. It should store all necessary information to determine whether to stop and provide a human-readable reason why it stopped, see get_reason(stopping_criterion). This function should return an empty string if the criterion has not yet indicated to stop.

The easiest example is the StopAfterIteration, which is initialized to a maximal number of iterations and returns true once the input k from above reaches this threshold. This stopping criterion does not store anything else, since the reason only requires the current iteration and the maximal one.

There is a list of common stopping criteria available. Stopping criteria that are specialized to a single solver can be found on the corresponding solver page.

Combining stopping criteria

For stopping criteria it is often useful to combine these.

Manopt.StoppingCriterionSet — Type
StoppingCriterionSet <: 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 StoppingCriterionSet is a common supertype for the two specific cases StopWhenAll and StopWhenAny. These are mapped to the operators & and |, respectively, so that stopping criteria can be easily combined.

Of course the main function to implement is the one of the new data structure (sc::StopWhenMyNewCriterion)(problem, state, k) itself.

Manopt.indicates_convergence — Function
indicates_convergence(c::StoppingCriterion)

Return whether 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, that is, of whether it currently indicates to stop; it is 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, or in other words, for StopWhenAny all its criteria have to indicate convergence for this to return true.
  • indicates_convergence(s1 & s2) is true, since s2 is fulfilled if this stops.
source
Manopt.has_converged — Function
has_converged(ams::AbstractManoptSolverState)

Return whether the solver has converged, based on the internal StoppingCriterion.

source
has_converged(c::StoppingCriterion)

Return whether a StoppingCriterion c has indicated to stop and is a stopping criterion that allows one to conclude that the corresponding solver has converged.

By default this is given by the static indicates_convergence(c) as well as the test whether the stopping criterion has stopped. For some stopping criteria, for example StopWhenAny a more advanced test can be done, that is more precise.

Examples

With s1=StopAfterIteration(20) and s2=StopWhenGradientNormLess(1e-7) we obtain

  • has_converged(s1) is always false (even if it has stopped)
  • has_converged(s2) is always true as soon as it has stopped
  • has_converged(s1 | s2) is true if it has stopped and s2 is the reason for that.
  • has_converged(s1 & s2) is true as soon as the algorithm stopped, since here s2 always has to be fulfilled as well.
source
Manopt.get_active_stopping_criteria — Function
get_active_stopping_criteria(c)

Return 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.

source
Manopt.requires_update — Function
requires_update(::Type{<:StoppingCriterion})

Return whether a StoppingCriterion has an internal state.

This is for example used when determining whether a StopWhenAll group of stopping criteria can maybe “stop early” to evaluate the single criteria.

By default this function returns the pessimistic answer of true. Stopping criteria that do not require internal updates can set this value to false.

source