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 k=0.
• time: stores the elapsed time
• at_iteration: indicates at which iteration (including k=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 k=0) the stopping criterion was fulfilled and is -1 while it is not fulfilled.

Constructor

StopAfterIteration(max_iterations)

initialize the functor to indicate to stop after max_iterations iterations.

StopWhenAll <: StoppingCriterionSet

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

Fields

• criteria: the tuple of StoppingCriterions that are combined
• at_iteration: the iteration at which this criterion last indicated to stop, -1 otherwise

Constructor

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

StopWhenAny <: StoppingCriterionSet

Store an array of StoppingCriterion elements and indicate 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 "").

Fields

• criteria: the tuple of StoppingCriterions that are combined
• at_iteration: the iteration at which this criterion last indicated to stop, -1 otherwise

Constructor

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

StopWhenChangeLess <: StoppingCriterion

Store a threshold when to stop looking at the norm of the change of the optimization variable from within a AbstractManoptSolverState s. That is, 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
• 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 by setting this value to missing.

The inverse_retraction_method can be used to approximate the distance by that inverse retraction together with a norm on the tangent space, if neither the distance nor the logarithmic map are available on M.

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

Constructor

StopWhenChangeLess(    M::AbstractManifold,    threshold::Float64;    storage::StoreStateAction=StoreStateAction(M; store_points=Tuple{: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 storage, 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.

StopWhenCostChangeLess <: StoppingCriterion

A stopping criterion to stop when the change of the cost function is less than a certain threshold.

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
• last_cost: the last cost value
• tolerance: the threshold for the change of the cost

Constructor

StopWhenCostChangeLess(tolerance::F)

Initialize the stopping criterion to a threshold tolerance for the change of the cost function.

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, s).

Constructor

StopWhenCostLess(ε::Real)

initialize the stopping criterion to a threshold ε.

StopWhenCostNaN <: StoppingCriterion

Stop the solver when the cost function of the optimization problem AbstractManoptProblem is NaN. The value is obtained using get_cost(p, s).

Constructor

StopWhenCostNaN()

initialize the stopping criterion with at_iteration equal to -1.

StopWhenCriterionWithIterationCondition <: StoppingCriterion

A stopping criterion that only evaluates a certain (inner) stopping criterion based on a condition on the iteration k. The condition is a function comp(k) -> Bool.

Example

comp = >(n) would only activate the wrapped stopping criterion after n iterations.

Fields

• stopping_criterion: the StoppingCriterion to wrap
• comp: the condition on the iteration k that decides whether the wrapped criterion is checked
• at_iteration: the iteration at which this criterion indicated to stop, -1 otherwise

Constructor

StopWhenCriterionWithIterationCondition(criterion::StoppingCriterion, n=0; comp = (>(n)))

Create a stopping criterion that only checks the inner criterion in those iterations k for which comp(k) is true. The n is ignored if you provide a manual functor comp.

Examples

A stopping criterion that indicates to stop when the gradient norm is small but only after the third iteration

StopWhenCriterionWithIterationCondition(StopWhenGradientNormLess(1e-6), 3)

You can also use the infix operators ≟ (\questeq on REPL), ⩻ (\ltquest), and ⩼ (\gtquest) to create such a criterion:

StopWhenGradientNormLess(1e-6) ≟ 3StopWhenGradientNormLess(1e-6) ⩻ 3StopWhenGradientNormLess(1e-6) ⩼ 3

These are equivalent to specifying comp = (==(3)), comp = (<(3)), and comp = (>(3)), respectively. Their interpretation is “the stopping criterion is only checked (asked) if the condition is met”.

StopWhenEntryChangeLess

Evaluate whether a certain field's 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
• last_change: the last change recorded in this stopping criterion

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::AbstractVectorTransportMethod: 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 by 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$ 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 gradient $X,Y ∈ T_{p}\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 manifolds that do not consist of components.

Constructor

StopWhenGradientChangeLess(    M::AbstractManifold,    ε::Float64;    storage::StoreStateAction=StoreStateAction(M; store_points=Tuple{:Iterate}, store_vectors=Tuple{:Gradient}),    vector_transport_method::VTM=default_vector_transport_method(M),    outer_norm::N=missing)

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

StopWhenGradientMappingNormLess <: StoppingCriterion

A stopping criterion based on the gradient mapping norm for proximal gradient methods.

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
• threshold: the threshold for the change to check (run under to stop)

Constructor

StopWhenGradientMappingNormLess(ε)

Create a stopping criterion with threshold ε for the gradient mapping for the proximal_gradient_method. That is, this criterion indicates to stop when the gradient mapping has a norm less than ε. The gradient mapping is defined as $G_λ(p) = -\frac{1}{λ}\log_p\bigl(T_λ(p)\bigr)$, where $T_λ(p) = \operatorname{prox}_{λ f}\bigl(\exp_p(-λ \operatorname{grad} f(p))\bigr)$ is the proximal mapping.

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 a function (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$ of points $p_i ∈ \mathcal{N}$. Then, denoting the outer_norm by $r$, the norm of a tangent vector like the current gradient $X ∈ T_{p}\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 the solver when the iterate of the optimization problem from within an AbstractManoptProblem contains NaN values. The value is obtained using get_iterate(s).

Constructor

StopWhenIterateNaN()

Initialize the stopping criterion.

StopWhenLagrangeMultiplierLess <: StoppingCriterion

A stopping criterion for Lagrange multipliers.

Currently this is meant for the convex_bundle_method and proximal_bundle_method, where based on the Lagrange multipliers an approximate (sub)gradient $g$ and an error estimate $ε$ are computed.

The mode=:both requires that both $ε$ and $\lvert g \rvert$ are smaller than their tolerances for the convex_bundle_method, and that $c$ and $\lvert d \rvert$ are smaller than their tolerances for the proximal_bundle_method.

The mode=:estimate requires that, for the convex_bundle_method $-ξ = \lvert g \rvert^2 + ε$ is less than a given tolerance. For the proximal_bundle_method, the equation reads $-ν = μ \lvert d \rvert^2 + c$.

Constructors

StopWhenLagrangeMultiplierLess(tolerance=1e-6; mode::Symbol=:estimate, names=nothing)

Create the stopping criterion for one of the modes mentioned. Note that tolerance can be a single number for the :estimate case, but a vector of two values is required for the :both mode. Here the first entry specifies the tolerance for $ε$ ($c$), the second the tolerance for $\lvert g \rvert$ ($\lvert d \rvert$), respectively.

Fields

• tolerances: the tolerances to check against
• values: the last values that were compared against the tolerances
• names: optional names for the values, used when reporting the reason
• mode: either :estimate or :both, see above
• at_iteration: the iteration at which this criterion indicated to stop, -1 otherwise

StopWhenProjectedNegativeGradientNormLess <: StoppingCriterion

A stopping criterion similar to StopWhenGradientNormLess, although it checks the norm of the projected negative gradient. It is primarily useful for optimization involving Hyperrectangle.

Fields

• norm: a function (M::AbstractManifold, p, X) -> ℝ computing the norm to use
• threshold: the threshold to indicate to stop when the norm is below this value
• last_change: the last norm recorded in this stopping criterion
• at_iteration: the iteration at which this criterion indicated to stop, -1 otherwise
• outer_norm: for manifolds with components, the norm used to combine the element-wise norms

On manifolds with boundary and manifolds with corners, for a tangent vector $X$, $-X$ might not be a valid tangent vector. As an example, consider the objective $f(x)=x^2$ on the interval $[1, 2]$. Its gradient at 1 is equal to 2, but because the point 1 is at the boundary of the interval, the projected negative gradient is equal to 0 because we can't go in the negative direction.

StopWhenRelativeAPosterioriCostChangeLessOrEqual <: StoppingCriterion

A stopping criterion to stop when

\[\frac{f_k - f_{k+1}}{\max(\lvert f_k \rvert, \lvert f_{k+1} \rvert, 1)} ≤ tol,\]

based on Eq. (1) in [ZBLN97].

Fields

• threshold: the threshold tol in the above formula.
• 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
• last_cost: the last cost value

Constructor

StopWhenRelativeAPosterioriCostChangeLessOrEqual(threshold::F)

Initialize the stopping criterion to a threshold for the change of the cost function.

StopWhenRelativeAPosterioriCostChangeLessOrEqual(; factr::Real=1.0e7)

Initialize threshold to factr * eps(typeof(factr)), following the convention in [ZBLN97].

StopWhenRepeated <: StoppingCriterion

A stopping criterion that indicates to stop when the (internal) stopping criterion it wraps has indicated to stop for n (consecutive) times.

Fields

• stopping_criterion: the StoppingCriterion to wrap
• n: the number of times the criterion has to indicate to stop
• count: the number of times the criterion has indicated to stop so far
• consecutive::Bool: indicate whether to count consecutive indications to stop or arbitrary.
• at_iteration: the iteration at which this criterion indicated to stop, -1 otherwise

Constructor

StopWhenRepeated(criterion::StoppingCriterion, n::Int; consecutive::Bool=true)criterion × ncross(sc::StoppingCriterion, n::Int)

Create a stopping criterion that indicates to stop when the criterion has indicated to stop n times (consecutively, if consecutive=true for the first constructor). Note that the cross product is in general noncommutative, and here only the order sc × n is possible.

Examples

A stopping criterion that indicates to stop whenever the gradient norm is less than 1e-6 for three consecutive iterations:

StopWhenRepeated(StopWhenGradientNormLess(1e-6), 3)StopWhenGradientNormLess(1e-6) × 3

A stopping criterion that indicates to stop whenever the gradient norm is less than 1e-6 at three iterations (not necessarily consecutive):

StopWhenRepeated(StopWhenGradientNormLess(1e-6), 3; consecutive=false)

StopWhenSmallerOrEqual <: StoppingCriterion

A functor for a stopping criterion, where the algorithm is stopped when a field of the solver state is smaller than or equal to a given minimum value.

Fields

• value: a Symbol naming the field of the solver state that has to fall under the threshold
• minValue: the threshold; if the field's value is smaller than or equal to it, the algorithm stops
• at_iteration: the iteration at which this criterion indicated to stop, -1 otherwise

Constructor

StopWhenSmallerOrEqual(value::Symbol, minValue)

initialize the functor to indicate to stop as soon as the field value is smaller than or equal to minValue.

StopWhenStepsizeLess <: StoppingCriterion

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

Fields

• threshold: the threshold below which the algorithm stops
• last_stepsize: the last step size recorded in this stopping criterion
• at_iteration: the iteration at which this criterion indicated to stop, -1 otherwise

Constructor

StopWhenStepsizeLess(ε)

initialize the stopping criterion to a threshold ε.

StopWhenSubgradientNormLess <: StoppingCriterion

A stopping criterion based on the current subgradient norm.

Fields

• at_iteration: the iteration at which this criterion indicated to stop, -1 otherwise
• threshold: the threshold below which the algorithm stops
• value: the last subgradient norm recorded in this stopping criterion

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 a StopWhenAll. If either s1 (or s2) is already a 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 a StopWhenAny. If either s1 (or s2) is already a 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))

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 threshold for the change of the tracked field 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::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 below which an algorithm shall stop.

set_parameter!(c::StopWhenGradientNormLess{F,TF}, :MinGradNorm, v::TF) where {F,TF<:Real}

Update the minimal gradient norm when an algorithm shall stop.

set_parameter!(c::StopWhenProjectedNegativeGradientNormLess{F,TF}, :MinGradNorm, v::TF) where {F, TF<:Real}

Update the minimal gradient norm when an algorithm shall stop.