# Stopping criteria

Stopping criteria are implemented as a `functor`

and inherit from the base type

`Manopt.StoppingCriterion`

— Type`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).

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

`Manopt.StoppingCriterionSet`

— Type`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.

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.at_iteration`

, to indicate at which iteration the stopping criterion (last) indicated to stop. `0`

refers to an indication *before* starting the algorithm, while any negative number meant the stopping criterion is not (yet) fulfilled. To can access a string giving the reason of stopping 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.StopAfter`

— Type`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.

`Manopt.StopAfterIteration`

— Type`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.

`Manopt.StopWhenAll`

— Type`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,...)
```

`Manopt.StopWhenAny`

— Type`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...)
```

`Manopt.StopWhenChangeLess`

— Type`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 `StoreStateAction`

`a`

, which is initialized to just store `:Iterate`

by default. You can also provide an inverse*retraction*method for the `distance`

or a manifold to use its default inverse retraction.

`Manopt.StopWhenCostLess`

— Type`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 `ε`

.

`Manopt.StopWhenCostNaN`

— Type`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.

`Manopt.StopWhenEntryChangeLess`

— Type`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]),
)
```

`Manopt.StopWhenGradientChangeLess`

— Type`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.

`Manopt.StopWhenGradientNormLess`

— Type`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**

`last_change`

store the last change`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.

`Manopt.StopWhenIterateNaN`

— Type`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.

`Manopt.StopWhenSmallerOrEqual`

— Type`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`

.

`Manopt.StopWhenStepsizeLess`

— Type`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 `ε`

.

`Manopt.StopWhenSubgradientNormLess`

— Type`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 `ε`

.

## 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(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))
```

`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(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))
```

`Manopt.get_active_stopping_criteria`

— Method`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.

`Manopt.get_reason`

— Method`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.

`Manopt.get_stopping_criteria`

— Method`get_stopping_criteria(c)`

return the array of internally stored `StoppingCriterion`

s for a `StoppingCriterionSet`

`c`

.

`Manopt.indicates_convergence`

— Method`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.

`Manopt.set_parameter!`

— Method`set_parameter!(c::StopAfter, :MaxTime, v::Period)`

Update the time period after which an algorithm shall stop.

`Manopt.set_parameter!`

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

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

`Manopt.set_parameter!`

— Method`set_parameter!(c::StopWhenChangeLess, :MinIterateChange, v::Int)`

Update the minimal change below which an algorithm shall stop.

`Manopt.set_parameter!`

— Method`set_parameter!(c::StopWhenCostLess, :MinCost, v)`

Update the minimal cost below which the algorithm shall stop

`Manopt.set_parameter!`

— Method`set_parameter!(c::StopWhenEntryChangeLess, :Threshold, v)`

Update the minimal cost below which the algorithm shall stop

`Manopt.set_parameter!`

— Method`set_parameter!(c::StopWhenGradientChangeLess, :MinGradientChange, v)`

Update the minimal change below which an algorithm shall stop.

`Manopt.set_parameter!`

— Method`set_parameter!(c::StopWhenGradientNormLess, :MinGradNorm, v::Float64)`

Update the minimal gradient norm when an algorithm shall stop

`Manopt.set_parameter!`

— Method`set_parameter!(c::StopWhenStepsizeLess, :MinStepsize, v)`

Update the minimal step size below which the algorithm shall stop

`Manopt.set_parameter!`

— Method`set_parameter!(c::StopWhenSubgradientNormLess, :MinSubgradNorm, v::Float64)`

Update the minimal subgradient norm when an algorithm shall stop