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 it last indicated to stop. Within Manopt.jl this is the field at_iteration. It should reset its internal variables when called with a negative number like k=-1. 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 reason 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 exceeds 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