Stepsizes

DistanceOverGradientsStepsize{R<:Real,P} <: Stepsize

A functor (problem, state, k, ...) -> s providing the Riemannian Distance over Gradients (RDoG) step size.

This step size is learning-rate-free: it adapts using the maximum distance travelled from the start point together with the accumulated squared gradient norms. See DistanceOverGradients for the mathematical details.

Fields

• initial_distance::R: initial distance estimate $ϵ>0$
• max_distance::R: tracked maximum distance $\bar r_t$
• gradient_sum::R: accumulated sum $G_t$
• initial_point: stored start point $p_0$
• use_curvature::Bool: toggle curvature correction $ζ_κ$
• sectional_curvature_bound::R: lower bound $κ$ used in $ζ_κ$ when use_curvature=true
• last_stepsize::R: last computed stepsize

Constructor

DistanceOverGradientsStepsize(M::AbstractManifold, p; kwargs...)

where p is the initial point, from which the distance is tracked.

Keyword arguments

• initial_distance=1e-3: initial estimate $ϵ$
• use_curvature=false: whether to use $ζ_κ$
• sectional_curvature_bound=0.0: lower curvature bound $κ$ (if known)

References

[DSN24]: Learning-Rate-Free Stochastic Optimization over Riemannian Manifolds (RDoG).

AdaptiveWNGradient(; kwargs...)
AdaptiveWNGradient(M::AbstractManifold; kwargs...)

A stepsize based on the adaptive gradient method introduced by [GS23].

Given a positive threshold $\hat{c} ∈ ℕ$, an minimal bound $b_{\text{min}} > 0$, an initial $b_0 ≥ b_{\text{min}}$, and a gradient reduction factor threshold $α ∈ [0,1)$.

Set $c_0=0$ and use $ω_0 = \lVert \operatorname{grad} f(p_0) \rVert_{p_0}$.

For the first iterate use the initial step size $s_0 = \frac{1}{b_0}$.

Then, given the last gradient $X_{k-1} = \operatorname{grad} f(x_{k-1})$, and a previous $ω_{k-1}$, the values $(b_k, ω_k, c_k)$ are computed using $X_k = \operatorname{grad} f(p_k)$ and the following cases

If $\lVert X_k \rVert_{p_k} ≤ αω_{k-1}$, then let $\hat{b}_{k-1} ∈ [b_{\text{min}},b_{k-1}]$ and set

\[(b_k, ω_k, c_k) = \begin{cases} \bigl(\hat{b}_{k-1}, \lVert X_k \rVert_{p_k}, 0 \bigr) & \text{ if } c_{k-1}+1 = \hat{c}\\\\ \bigl( b_{k-1} + \frac{\lVert X_k \rVert_{p_k}^2}{b_{k-1}}, ω_{k-1}, c_{k-1}+1 \Bigr) & \text{ if } c_{k-1}+1<\hat{c}\end{cases}\]

If $\lVert X_k \rVert_{p_k} > αω_{k-1}$, the set

\[(b_k, ω_k, c_k) = \Bigl( b_{k-1} + \frac{\lVert X_k \rVert_{p_k}^2}{b_{k-1}}, ω_{k-1}, 0 \Bigr)\]

and return the step size $s_k = \frac{1}{b_k}$.

Note that for $α=0$ this is the Riemannian variant of WNGRad.

Keyword arguments

• adaptive=true: switches the gradient_reductionα(iftrue) to0`.
• alternate_bound = (bk, hat_c) -> min(gradient_bound == 0 ? 1.0 : gradient_bound, max(minimal_bound, bk / (3 * hat_c)): how to determine $\hat{k}_k$ as a function of (bmin, bk, hat_c) -> hat_bk
• count_threshold=4: an Integer for $\hat{c}$
• gradient_reduction::R=adaptive ? 0.9 : 0.0: the gradient reduction factor threshold $α ∈ [0,1)$
• gradient_bound=norm(M, p, X): the bound $b_k$.
• minimal_bound=1e-4: the value $b_{\text{min}}$
• p::P =rand(M): a point on the manifold $\mathcal{M}$ only used to define the gradient_bound
• X::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$ only used to define the gradient_bound

ArmijoLinesearch(; kwargs...)
ArmijoLinesearch(M::AbstractManifold; kwargs...)

Specify a step size that performs an Armijo line search. It is given a function $f:\mathcal{M}→ℝ$ and its Riemannian gradient $\operatorname{grad}f: \mathcal{M}→T\mathcal{M}$, the current point $p∈\mathcal{M}$ and a search direction $X∈T_{p}\mathcal{M}$.

Then the step size $s$ is found by reducing the initial step size $s$ until

\[f(\operatorname{retr}_p(sX)) ≤ f(p) - τs ⟨ X, \operatorname{grad}f(p) ⟩_p\]

is fulfilled, for a sufficient decrease value $τ ∈ (0,1)$.

To be a bit more optimistic, if $s$ already fulfils this, a first search is done, increasing the given $s$ until for a first time this step does not hold.

Overall, a step size is sought that provides enough decrease, see [Bou23, p. 58] for more information.

Keyword arguments

• additional_decrease_condition=(M, p) -> true: specify an additional criterion that has to be met to accept a step size in the decreasing loop
• additional_increase_condition::IF=(M, p) -> true: specify an additional criterion that has to be met to accept a step size in the (initial) increase loop
• candidate_point=allocate_result(M, rand): specify a point to be used as memory for the candidate points.
• contraction_factor=0.95: how to update $s$ in the decrease step
• initial_stepsize=1.0: specify an initial step size
• initial_guess=ArmijoInitialGuess(): Compute the initial step size of a line search based on this function. See AbstractInitialLinesearchGuess for details.
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stop_when_stepsize_less=0.0: a safeguard, stop when the decreasing step is below this (nonnegative) bound.
• stop_when_stepsize_exceeds=max_stepsize(M): a safeguard to not choose a too long step size when initially increasing
• stop_increasing_at_step=100: stop the initial increasing loop after this amount of steps. Set to 0 to never increase in the beginning
• stop_decreasing_at_step=1000: maximal number of Armijo decreases / tests to perform
• sufficient_decrease=0.1: the sufficient decrease parameter $τ$

For the stop safe guards you can pass :Messages to a debug= to see @info messages when these happen.

ConstantLength(s; kwargs...)
ConstantLength(M::AbstractManifold, s; kwargs...)

Specify a Stepsize that is constant.

Input

• M (optional)
• s=min(injectivity_radius(M)/2, 1.0): the length to use.

Keyword argument

• type::Symbol=:relative specify the type of constant step size. Possible values are
  • :relative – scale the gradient tangent vector $X$ to $s*X$
  • :absolute – scale the gradient to an absolute step length $s$, that is $\frac{s}{\lVert X \rVert}X$

CubicBracketingLinesearch(; kwargs...)
CubicBracketingLinesearch(M::AbstractManifold; kwargs...)

A functor representing the curvature minimizing cubic bracketing scheme introduced in [Hag89]. Firstly, a bracket $[a,b]$ is generated by multiplying $t_0$ chosen as last_stepsize (or in case of the first iteration initial_stepsize) repeatedly with the stepsize_increase > 1 until the bracket conditions

\[ ϕ'(a)(b-a) < 0 \quad \text{and} \quad ϕ(a) ≤ ϕ(b).\]

are satisfied by either $[a,b] = [t_{k-1},t_k]$, $[a,b] = [t_k,t_{k-1}]$, $[a,b] = [0,t_k]$, or $[a,b] = [t_k,0]$. Here, $ϕ(t)$ denotes the cost function when performing a step with size $t$ into direction $η$. Over the iteration, the bracket $[a,b]$ is repeatedly updated using a cubic polynomial using values of $ϕ, ϕ'$ at $a,b$. The update value $c$ is the local minimum of the polynomial, and the bracket condition ensures that it lies in between $a$ and $b$. We note that the update strategy taken from [Hag89] ensures that the updated bracket satisfies the bracket condition.

If the parameter hybrid is set to true, the hybrid approach from [Hag89] is activated, which prevents slow convergence in edge cases.

The algorithm terminates if at any point the found candidate stepsize suffices the curvature condition induced by sufficient_curvature, or the bracket $[a,b]$ is smaller than min_bracket_width.

Keyword arguments

• p::P =rand(M): a point on the manifold $\mathcal{M}$ to store an interim result
• initial_stepsize=1.0: the step size to start the search with
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize_increase=1.5: step size increase factor $>1$
• max_iterations=100: maximum number of iterations
• sufficient_curvature=0.2: target reduction of the curvature $(0,1)$
• min_bracket_width=1e-4: minimal size of the bracket $[a,b]$
• hybrid=true: use the hybrid strategy
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

DecreasingLength(; kwargs...)
DecreasingLength(M::AbstractManifold; kwargs...)

Specify a Stepsize that is decreasing as $s_k = \frac{(l - ak)f^k}{(k+s)^e}$ with the following

Keyword arguments

• exponent=1.0: the exponent $e$ in the denominator
• factor=1.0: the factor $f$ in the nominator
• length=isinf(manifold_dimension(M)) ? 1.0 : manifold_dimension(M)/2: the initial step size $l$.
• subtrahend=0.0: a value $a$ that is subtracted every iteration
• shift=0.0: shift the denominator iterator $k$ by $s$.
• type::Symbol=:relative specify the type of step size. Possible values are
  • :relative – scale the gradient tangent vector $X$ to $s_k*X$
  • :absolute – scale the gradient to an absolute step length $s_k$, that is $\frac{s_k}{\lVert X \rVert}X$

DistanceOverGradients(; kwargs...)
DistanceOverGradients(M::AbstractManifold; kwargs...)

Create a factory for the DistanceOverGradientsStepsize, the Riemannian Distance over Gradients (RDoG) learning-rate-free stepsize from [DSN24]. It adapts without manual tuning, by combining the maximum distance from the start point with the accumulated gradient norms, optionally corrected by the geometric curvature term $ζ_κ$.

Definitions used by the implementation:

• $\bar r_t := \max(\,ϵ,\, \max_{0\le s\le t} d(p_0, p_s)\,)$ tracks the maximum geodesic distance from the initial point $p_0$ using the current iterate $p_t$.
• $G_t := \displaystyle\sum_{s=0}^t \lVert g_s \rVert^2$, where $g_s = \operatorname{grad} f(p_s)$.

At iteration $t$ the stepsize used here is

\[η_t = \begin{cases} \frac{\bar r_t}{\sqrt{G_t}}, & \text{if we do not use curvature,}\\ \frac{\bar r_t}{\sqrt{\,ζ_κ(\bar r_t)\,}\,\sqrt{G_t}}, & \text{if we use curvature.} \end{cases}\]

with the geometric curvature function $ζ_κ(d)$ defined in geometric_curvature_function. The initialization in this implementation follows the paper: on the first call ($t=0$), we set $G_0=\lVert g_0\rVert^2$, $\bar r_0 = ϵ$ and take

\[η_0 = \begin{cases} \frac{ϵ}{\lVert g_0\rVert}, & \text{if we do not use curvature,}\\ \frac{ϵ}{\sqrt{\,ζ_κ(ϵ)\,}\,\lVert g_0\rVert}, & \text{if we use curvature.} \end{cases}\]

On subsequent calls, the state is updated as implemented: $G_t ← G_{t-1} + \lVert g_t\rVert^2$ and $\bar r_t ← \max(\bar r_{t-1}, d(p_0,p_t))$.

Keyword arguments

• initial_distance=1e-3: initial distance estimate $ϵ$
• use_curvature=false: whether to include $ζ_κ$
• sectional_curvature_bound=0.0: curvature lower bound $κ$ (if known)

HagerZhangLinesearch(; kwargs...)
HagerZhangLinesearch(M::AbstractManifold; kwargs...)

A functor representing the line search introduced in [HZ06b].

It finds a step size satisfying the (standard or approximate) Wolfe conditions by bracketing and then narrowing the bracket with secant and bisection steps.

The following changes were made to the original algorithm from the paper:

1. The algorithm bails out early of a secant update that is too close to one of the end points and switches to bisection. Original algorithm performs a similar check at a later stage. This precaution prevents a non-productive evaluation of the objective.
2. Added start_enforcing_wolfe_conditions_at_bracketing_iteration, since with a very low stepsize initialization that satisfies Wolfe conditions we might accept the initial stepsize and not notice that bracketing could help us reach the minimum earlier. Setting start_enforcing_wolfe_conditions_at_bracketing_iteration to 1 reproduces the behavior of the original paper. For example a static initial stepsize equal to 1.0 could benefit from having this parameter increased.
3. The paper isn't entirely clear on what the final stepsize to return is. This implementation returns the last evaluated stepsize.
4. The original algorithm doesn't specify what to do when the maximum stepsize is reached during the bracketing phase with a negative slope and an improvement over the initial point. This implementation allows for an early termination in this case, which seems reasonable since we can't expand the bracket anymore and this point is likely close to the minimum. By default this early termination is allowed, but it can be turned off via allow_early_maxstep_termination in which case the algorithm continues with the main loop even in this case.

Keyword arguments

• candidate_point::P =rand(M): a point on the manifold $\mathcal{M}$ as temporary storage for candidates
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• initial_guess::AbstractInitialLinesearchGuess=HagerZhangInitialGuess(): initial linesearch guess strategy
• initial_last_stepsize::Real = NaN: initial value for the stored last stepsize
• initial_last_cost::Real = NaN: initial value for the stored last cost
• stepsize_limit::Real = Inf: upper bound for trial stepsizes during bracketing
• candidate_direction = zero_vector(M, candidate_point): storage for transported directions
• max_bracket_iterations::Int = 10: maximum number of bracketing iterations
• start_enforcing_wolfe_conditions_at_bracketing_iteration::Int = initial_guess isa ConstantInitialGuess ? 2 : 1: bracketing iteration number at which Wolfe conditions are started to be enforced; setting to 1 may cause no bracketing to occur when the initial guess satisfies the Wolfe conditions.
• max_function_evaluations::Int = 20: maximum number of function evaluations per linesearch
• allow_early_maxstep_termination::Bool = true: whether to allow early termination when the maximum stepsize is reached with negative slope and an improvement over the initial point.
• wolfe_condition_mode::Symbol = :adaptive: one of :standard, :approximate, or :adaptive. Selects between (T1) and (T2) conditions in [HZ06b].
• ϵ::Real = 1.0e-6: initial allowed increase in function value in termination condition (T2). Allowed range: ϵ >= 0.
• δ::Real = 0.1: parameter for approximate Wolfe condition. Allowed range: 0 < δ < 0.5 and δ <= σ.
• σ::Real = 0.9: curvature condition parameter. Allowed range: δ <= σ < 1.
• ω::Real = 1.0e-3: interpolation safeguard parameter. Allowed range: 0 <= ω <= 1.
• θ::Real = 0.5: bisection update parameter. Allowed range: 0 < θ < 1.
• γ::Real = 0.66: determines when a bisection step is performed instead of secant. Allowed range: 0 < γ < 1.
• ρ::Real = 5.0: bracketing expansion factor. Allowed range: ρ > 1.
• Δ::Real = 0.7: Parameter controlling the rate of change of Qₖ. Allowed range: 0 <= Δ <= 1.
• secant_acceptance_ratio::Real = 1.0e-8: minimum relative interval length for accepting secant step. Allowed range: secant_acceptance_ratio >= 0. In case of rejection, a bisection step is performed instead.

NonmonotoneLinesearch(; kwargs...)
NonmonotoneLinesearch(M::AbstractManifold; kwargs...)

A functor representing a nonmonotone line search using the Barzilai-Borwein step size [IP17].

This method first computes

\[y_{k} = \operatorname{grad}f(p_{k}) - \mathcal T_{p_k←p_{k-1}}\operatorname{grad}f(p_{k-1})\]

and

\[s_{k} = - α_{k-1} ⋅ \mathcal T_{p_k←p_{k-1}}\operatorname{grad}f(p_{k-1}),\]

where $α_{k-1}$ is the step size computed in the last iteration and $\mathcal T_{⋅←⋅}$ is a vector transport. Then the Barzilai—Borwein step size is

\[α_k^{\text{BB}} = \begin{cases} \min(α_{\text{max}}, \max(α_{\text{min}}, τ_{k})), & \text{if} ⟨s_{k}, y_{k}⟩_{p_k} > 0,\\\\ α_{\text{max}}, & \text{else,}\end{cases}\]

where

\[τ_{k} = \frac{⟨s_{k}, s_{k}⟩_{p_k}}{⟨s_{k}, y_{k}⟩_{p_k}},\]

if the direct strategy is chosen, or

\[τ_{k} = \frac{⟨s_{k}, y_{k}⟩_{p_k}}{⟨y_{k}, y_{k}⟩_{p_k}},\]

in case of the inverse strategy or an alternation between the two in cases for the alternating strategy. Then find the smallest $h = 0, 1, 2, …$ such that

\[f(\operatorname{retr}_{p_k}(- σ^h α_k^{\text{BB}} \operatorname{grad}f(p_k))) ≤ \max_{1 ≤ j ≤ \max(k+1,m)} f(p_{k+1-j}) - γ σ^h α_k^{\text{BB}} ⟨\operatorname{grad}f(p_k), \operatorname{grad}f(p_k)⟩_{p_k},\]

where $σ ∈ (0,1)$ is a step length reduction factor, $m$ is the number of iterations after which the function value has to be lower than the current one and $γ ∈ (0,1)$ is the sufficient decrease parameter. Finally the step size is computed as

\[α_k = σ^h α_k^{\text{BB}}.\]

Keyword arguments

• p::P =rand(M): a point on the manifold $\mathcal{M}$ to store an interim result
• initial_guess = (problem, state, k, last_stepsize, η) -> k == 0 ? 1.0 : last_stepsize: a function to provide an initial guess for the step size
• memory_size=10: number of iterations after which the cost value needs to be lower than the current one
• bb_min_stepsize=1e-3: lower bound for the Barzilai-Borwein step size, greater than zero
• bb_max_stepsize=1e3: upper bound for the Barzilai-Borwein step size, greater than bb_min_stepsize
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• strategy=:direct: defines if the new step size is computed using the :direct, :inverse or :alternating strategy
• storage=StoreStateAction(M; store_fields=[:Iterate, :Gradient]): increase efficiency by using a StoreStateAction for :Iterate and :Gradient.
• stepsize_reduction=0.5: step size reduction factor contained in the interval $(0,1)$
• sufficient_decrease=1e-4: sufficient decrease parameter contained in the interval $(0,1)$
• stop_when_stepsize_less=0.0: smallest stepsize when to stop (the last one before is taken)
• stop_when_stepsize_exceeds=max_stepsize(M): largest stepsize when to stop to avoid leaving the injectivity radius
• stop_increasing_at_step=100: last step to increase the stepsize (phase 1),
• stop_decreasing_at_step=1000: last step size to decrease the stepsize (phase 2),

Polyak(; kwargs...)
Polyak(M::AbstractManifold; kwargs...)

Compute a step size according to a method proposed by Polyak, cf. the Dynamic step size discussed in Section 3.2 of [Ber15]. This has been generalized here to both the Riemannian case and to approximate the minimum cost value.

Let $f_{\text{best}}$ be the best cost value seen until now during some iterative optimization algorithm and let $γ_k$ be a sequence of numbers that is square summable, but not summable.

Then the step size computed here reads

\[s_k = \frac{f(p^{(k)}) - f_{\text{best}} + γ_k}{\lVert ∂f(p^{(k)}) \rVert},\]

where $∂f$ denotes a nonzero-subgradient of $f$ at the current iterate $p^{(k)}$.

Constructor

Polyak(; γ = k -> 1/k, initial_cost_estimate=0.0)

initialize the Polyak stepsize to a certain sequence and an initial estimate of $f_{\text{best}}$.

WolfePowellBinaryLinesearch(; kwargs...)
WolfePowellBinaryLinesearch(M::AbstractManifold; kwargs...)

Perform a linesearch to fulfill both the Armijo-Goldstein conditions for some given sufficient decrease coefficient $c_1$ and some sufficient curvature condition coefficient $c_2$. Compared to WolfePowellLinesearch which tries a simpler method, this linesearch performs the following algorithm

With

\[A(t) = f(p_+) ≤ f(p) + c_1 t ⟨\operatorname{grad}f(p), X⟩_{p} \quad\text{ and }\quad W(t) = ⟨\operatorname{grad}f(p_+), \mathcal T_{p_+←p}X⟩_{p_+} ≥ c_2 ⟨X, \operatorname{grad}f(p)⟩_p,\]

where $p_+ =\operatorname{retr}_p(tX)$ is the current trial point, and $\mathcal T_{⋅←⋅}$ denotes a vector transport. Then the following Algorithm is performed similar to Algorithm 7 from [Hua14]

1. set $α=0$, $β=∞$ and $t=1$.
2. While either $A(t)$ does not hold or $W(t)$ does not hold do steps 3-5.
3. If $A(t)$ fails, set $β=t$.
4. If $A(t)$ holds but $W(t)$ fails, set $α=t$.
5. If $β<∞$ set $t=\frac{α+β}{2}$, otherwise set $t=2α$.

Keyword arguments

• sufficient_decrease=1e-4
• sufficient_curvature=0.999
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stop_when_stepsize_less=0.0: smallest stepsize when to stop (the last one before is taken)
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

WolfePowellLinesearch(; kwargs...)
WolfePowellLinesearch(M::AbstractManifold; kwargs...)

Perform a linesearch to fulfill both the Armijo-Goldstein conditions

\[f\bigl( \operatorname{retr}_{p}(αX) \bigr) ≤ f(p) + c_1 α_k ⟨\operatorname{grad} f(p), X⟩_{p}\]

as well as the Wolfe conditions

\[\frac{\mathrm{d}}{\mathrm{d}t} f\bigl(\operatorname{retr}_{p}(tX)\bigr) \Big\vert_{t=α} ≥ c_2 \frac{\mathrm{d}}{\mathrm{d}t} f\bigl(\operatorname{retr}_{p}(tX)\bigr)\Big\vert_{t=0}.\]

for some given sufficient decrease coefficient $c_1$ and some sufficient curvature condition coefficient $c_2$.

This is adopted from [NW06, Section 3.1]

Keyword arguments

• sufficient_decrease=1e-4
• sufficient_curvature=0.999
• p::P =rand(M): a point on the manifold $\mathcal{M}$ as temporary storage for candidates
• X::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$ as type of memory allocated for the candidate direction
• max_stepsize=max_stepsize(M): largest stepsize allowed here.
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stop_when_stepsize_less=0.0: smallest stepsize when to stop (the last one before is taken)
• stop_increasing_at_step=100: for the initial increase test (s_plus), stop after these many steps
• stop_decreasing_at_step=1000: for the initial decrease test (s_minus), stop after these many steps
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

AdaptiveWNGradientStepsize{I<:Integer,R<:Real,F<:Function} <: Stepsize

A functor (problem, state, k, X) -> s implementing the adaptive gradient method introduced by [GS23]. See AdaptiveWNGradient for the mathematical details.

Fields

• count_threshold::I: an Integer for $\hat{c}$
• minimal_bound::R: the value for $b_{\text{min}}$
• alternate_bound::F: how to determine $\hat{b}_k$ as a function of (bmin, bk, hat_c) -> hat_bk
• gradient_reduction::R: the gradient reduction factor threshold $α ∈ [0,1)$
• gradient_bound::R: the bound $b_k$.
• weight::R: $ω_k$, initialized to $ω_0 =$ norm(M, p, X) if this is not zero, 1.0 otherwise.
• count::I: $c_k$, initialized to $c_0 = 0$.

Constructor

AdaptiveWNGradientStepsize(M::AbstractManifold; kwargs...)

Keyword arguments

• adaptive=true: switches the gradient_reduction $α$ (if true) to 0.
• alternate_bound = (bk, hat_c) -> min(gradient_bound == 0 ? 1.0 : gradient_bound, max(minimal_bound, bk / (3 * hat_c)))
• count_threshold=4
• gradient_reduction::R=adaptive ? 0.9 : 0.0
• gradient_bound=norm(M, p, X)
• minimal_bound=1e-4
• p::P =rand(M): a point on the manifold $\mathcal{M}$ only used to define the gradient_bound
• X::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$ only used to define the gradient_bound

ArmijoInitialGuess <: AbstractInitialLinesearchGuess

Implement the initial guess for an Armijo line search.

The initial step size is chosen as min(l, max_stepsize(M, p) / norm(M, p, η)), where l is the last step size used, p the current point and η the search direction.

The default provided is based on the max_stepsize(M, p).

Constructor

ArmijoInitialGuess()

ArmijoLinesearchStepsize <: Linesearch

A functor (problem, state, k, X; kwargs...) -> s to provide an Armijo line search to compute a step size, based on the search direction X.

Fields

• additional_decrease_condition: specify a condition a new point has to additionally fulfill. The default accepts all points.

• additional_increase_condition: specify a condition that additionally to checking a valid increase has to be fulfilled. The default accepts all points.

• candidate_point: to store an interim result

• initial_stepsize: an initial step size

• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions

• contraction_factor: factor the step size is multiplied with in the backtracking loop

• sufficient_decrease: gain within Armijo's rule

• last_stepsize: the last step size to start the search with

• initial_guess::F: a function to provide an initial guess for the step size, it maps (problem, state, k, last_stepsize, η) -> α_0 based on

  • an AbstractManoptProblem problem
  • an AbstractManoptSolverState state
  • the current iteration k
  • the last step size last_stepsize
  • the search direction η

  and should at least accept the keywords

  • lf0 =get_cost(problem, get_iterate(state)): the current cost at p, here interpreted as the initial point of f along the line search direction
  • Dlf0 =get_differential(problem, get_iterate(state), η): the directional derivative at point p in direction η

• messages::NamedTuple: a named tuple to store possible StepsizeMessage about the stepsize search.

• stop_when_stepsize_less: smallest stepsize when to stop (the last one before is taken)

• stop_when_stepsize_exceeds: largest stepsize when to stop.

• stop_increasing_at_step: last step to increase the stepsize (phase 1),

• stop_decreasing_at_step: last step size to decrease the stepsize (phase 2),

Pass :Messages to a debug= to see @infos when these happen.

Constructor

ArmijoLinesearchStepsize(M::AbstractManifold; kwargs...)

where the fields are set from the keyword arguments below and the retraction defaults to the default retraction on M.

Keyword arguments

• candidate_point=allocate_result(M, rand)
• initial_stepsize=1.0
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• contraction_factor=0.95
• sufficient_decrease=0.1
• last_stepsize=initial_stepsize
• initial_guess=ArmijoInitialGuess()
• stop_when_stepsize_less=0.0: stop when the stepsize decreased below this value.
• stop_when_stepsize_exceeds=max_stepsize(M): provide an absolute maximal step size.
• stop_increasing_at_step=100: for the initial increase test, stop after these many steps
• stop_decreasing_at_step=1000: in the backtrack, stop after these many steps

ConstantInitialGuess{TF} <: AbstractInitialLinesearchGuess

Implement a constant initial guess for line searches.

Constructor

ConstantInitialGuess(α::TF)

where α is the constant initial step size.

ConstantStepsize <: Stepsize

A functor (problem, state, ...) -> s to provide a constant step size s.

Fields

• length: constant value for the step size
• type: a symbol that indicates whether the stepsize is relatively (:relative), with respect to the gradient norm, or absolutely (:absolute) constant.

Constructors

ConstantStepsize(s::Real, t::Symbol=:relative)

initialize the stepsize to a constant s of type t.

ConstantStepsize(    M::AbstractManifold=DefaultManifold(),    s=min(injectivity_radius(M)/2, 1.0);    type::Symbol=:relative)

CubicBracketingLinesearchStepsize{R<:Real,I<:Integer,TRM,VTM,P,T} <: Linesearch

Do a bracketing line search to find a step size $α$ that finds a local minimum along the search direction $X$ starting from $p$, utilizing cubic polynomial interpolation. See CubicBracketingLinesearch for the mathematical details.

Fields

• candidate_point::P: a point on the manifold $\mathcal{M}$ as temporary storage for candidates
• candidate_direction::T: temporary storage for the transported search direction
• initial_stepsize::R: the step size to start the search with
• last_stepsize::R
• retraction_method::AbstractRetractionMethod: a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize_increase::R: step size increase factor $>1$
• max_iterations::I: maximum number of iterations
• sufficient_curvature::R: target reduction of the curvature $(0,1)$
• min_bracket_width::R: minimal size of the bracket $[a,b]$
• hybrid::Bool: use the hybrid strategy
• max_stepsize::R: maximal stepsize
• vector_transport_method::AbstractVectorTransportMethod: a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

Constructor

CubicBracketingLinesearchStepsize(M::AbstractManifold; kwargs...)CubicBracketingLinesearchStepsize(M::AbstractManifold, p; kwargs...)

Keyword arguments

• candidate_point::P =rand(M): a point on the manifold $\mathcal{M}$ as temporary storage for candidates
• initial_stepsize=1.0: the step size to start the search with
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize_increase=1.5: step size increase factor $>1$
• max_iterations=100: maximum number of iterations
• sufficient_curvature=0.2: target reduction of the curvature $(0,1)$
• min_bracket_width=1e-4: minimal size of the bracket $[a,b]$
• hybrid=true: use the hybrid strategy
• max_stepsize= max_stepsize(M): maximal stepsize
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

DecreasingStepsize(M::AbstractManifold; kwargs...)

A functor (problem, state, ...) -> s to provide a decreasing step size s.

Fields

• exponent: a value $e$, the exponent the shifted iteration number is raised to in the denominator
• factor: a value $f$ to multiply the initial step size with every iteration
• length: the initial step size $l$.
• subtrahend: a value $a$ that is subtracted every iteration
• shift: shift the denominator iterator $k$ by $s$.
• type: a symbol that indicates whether the stepsize is relatively (:relative), with respect to the gradient norm, or absolutely (:absolute) constant.

In total the complete formulae reads for the $k$th iterate as

\[s_k = \frac{(l - k a)f^k}{(k + s)^e}\]

and hence the default simplifies to just $s_k = \frac{l}{k}$

Constructor

DecreasingStepsize(M::AbstractManifold;    length=isinf(manifold_dimension(M)) ? 1.0 : manifold_dimension(M)/2,    factor=1.0,    subtrahend=0.0,    exponent=1.0,    shift=0.0,    type=:relative,)

initializes all fields, where none of them is mandatory. The length defaults to half the manifold dimension, or to $1$ if that dimension is infinite.

HagerZhangInitialGuess{TF <: Real, TPN, TVN} <: AbstractInitialLinesearchGuess

Initial line search guess from the paper [HZ06b], following their initial-guess procedure I0. The line search was adapted to the Riemannian setting by introducing customizable norms for points and tangent vectors and a maximum stepsize alphamax.

HagerZhangLinesearchStepsize{TF<:Real,TIG,TRM,TVTM,TP,TX} <: Linesearch

Do a bracketing line search to find a step size $α$ that finds a local minimum along the search direction $X$ starting from $p$, utilizing cubic polynomial interpolation using the method described in [HZ06b]. The function secant is used to find the minimum of the cubic polynomial fitted to values of the cost function and its derivative at the endpoints of the current interval. See HagerZhangLinesearch for the mathematical details.

Fields

• candidate_point::P: a point on the manifold $\mathcal{M}$ as temporary storage for candidates
• retraction_method::AbstractRetractionMethod: a retraction $\operatorname{retr}$ to use, see the section on retractions
• vector_transport_method::AbstractVectorTransportMethod: a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• initial_guess: see keyword arguments of HagerZhangLinesearch for details.
• stepsize_limit: see keyword arguments of HagerZhangLinesearch for details.
• max_bracket_iterations: see keyword arguments of HagerZhangLinesearch for details.
• start_enforcing_wolfe_conditions_at_bracketing_iteration: see keyword arguments of HagerZhangLinesearch for details.
• allow_early_maxstep_termination: see keyword arguments of HagerZhangLinesearch for details.
• wolfe_condition_mode: see keyword arguments of HagerZhangLinesearch for details.
• ϵ, δ, σ, ω, θ, γ, ρ, Δ: see keyword arguments of HagerZhangLinesearch for details.
• secant_acceptance_ratio: see keyword arguments of HagerZhangLinesearch for details.
• candidate_direction, temporary_tangent: as temporary storage for tangent vectors
• triples: temporary storage for function and derivative evaluations
• last_evaluation_index: to keep track of the number of evaluations performed so far; points at the last filled entry of triples.
• Qₖ, Cₖ: to keep track of the parameters of the Wolfe condition when in adaptive mode
• current_mode: to keep track of the current Wolfe condition mode when in adaptive mode
• last_stepsize: last stepsize computed since reset
• last_cost: last cost value computed since reset
• ϵₖ: the current ϵ parameter used in the approximate Wolfe condition and bracketing

Constructor

HagerZhangLinesearchStepsize(M::AbstractManifold; kwargs...)

NonmonotoneLinesearchStepsize{P,T,R<:Real,I<:Integer,TRM,VTM,TSSA,MSGS,IG} <: Linesearch

A functor representing a nonmonotone line search using the Barzilai-Borwein step size [IP17].

Fields

• initial_guess::F: a function to provide an initial guess for the step size, it maps (problem, state, k, last_stepsize, η) -> α_0 based on

  • an AbstractManoptProblem problem
  • an AbstractManoptSolverState state
  • the current iteration k
  • the last step size last_stepsize
  • the search direction η

  and should at least accept the keywords

  • lf0 =get_cost(problem, get_iterate(state)): the current cost at p, here interpreted as the initial point of f along the line search direction
  • Dlf0 =get_differential(problem, get_iterate(state), η): the directional derivative at point p in direction η

• memory_size: number of iterations after which the cost value needs to be lower than the current one

• bb_min_stepsize: lower bound for the Barzilai-Borwein step size, greater than zero

• bb_max_stepsize: upper bound for the Barzilai-Borwein step size, greater than bb_min_stepsize

• last_stepsize: the last computed stepsize

• retraction_method::AbstractRetractionMethod: a retraction $\operatorname{retr}$ to use, see the section on retractions

• strategy: defines if the new step size is computed using the :direct, :inverse or :alternating strategy

• storage: (for :Iterate and :Gradient) a StoreStateAction

• stepsize_reduction: step size reduction factor contained in the interval (0,1)

• sufficient_decrease: sufficient decrease parameter contained in the interval (0,1)

• vector_transport_method::AbstractVectorTransportMethod: a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

• candidate_point: to store an interim result

• stop_when_stepsize_less: smallest stepsize when to stop (the last one before is taken)

• stop_when_stepsize_exceeds: largest stepsize when to stop.

• stop_increasing_at_step: last step to increase the stepsize (phase 1),

• stop_decreasing_at_step: last step size to decrease the stepsize (phase 2),

Constructor

NonmonotoneLinesearchStepsize(M::AbstractManifold; kwargs...)NonmonotoneLinesearchStepsize(M::AbstractManifold, p; kwargs...)

Keyword arguments

• p=allocate_result(M, rand): to store an interim result
• initial_guess = (problem, state, k, last_stepsize, η) -> k == 0 ? 1.0 : last_stepsize function to provide an initial guess for the stepsize
• memory_size=10
• bb_min_stepsize=1e-3
• bb_max_stepsize=1e3
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• strategy=:direct
• storage=StoreStateAction(M; store_fields=[:Iterate, :Gradient])
• stepsize_reduction=0.5
• sufficient_decrease=1e-4
• stop_when_stepsize_less=0.0
• stop_when_stepsize_exceeds=max_stepsize(M)
• stop_increasing_at_step=100
• stop_decreasing_at_step=1000
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

PolyakStepsize <: Stepsize

A functor (problem, state, ...) -> s to provide a step size due to Polyak, cf. Section 3.2 of [Ber15].

Fields

• γ : a function k -> ... representing a sequence.
• best_cost_value : storing the best cost value

Constructor

PolyakStepsize(; γ = k -> 1/k,  initial_cost_estimate=0.0)

Construct a stepsize of Polyak type.

See also

Polyak

StepsizeMessage{TBound, TS}

A message struct to hold stepsize information, when e.g. a step size underflow happens at a certain iteration.

Fields

• at_iteration::Int: The iteration at which the message was set
• bound::TBound: The bound that was hit
• value::TS: The corresponding value that either caused the message or provides additional information

Constructor

StepsizeMessage(; bound::TBound = 0.0, value::TS = 0.0)

UnivariateTriple{R <: Real}

Triple of stepsize, function value and derivative value.

Fields

• t::R: stepsize
• f::R: cost at stepsize t
• df::R: derivative of the cost at stepsize t

WolfePowellBinaryLinesearchStepsize{TRM,VTM,F} <: Linesearch

Do a backtracking line search to find a step size $α$ that fulfils the Wolfe conditions along a search direction $X$ starting from $p$. See WolfePowellBinaryLinesearch for the math details.

Fields

• sufficient_decrease::F, sufficient_curvature::F: two constants in the line search
• last_stepsize::F: the last computed stepsize
• retraction_method::AbstractRetractionMethod: a retraction $\operatorname{retr}$ to use, see the section on retractions
• stop_when_stepsize_less::F: a safeguard to stop when the stepsize gets too small
• vector_transport_method::AbstractVectorTransportMethod: a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

Constructor

WolfePowellBinaryLinesearchStepsize(M::AbstractManifold; kwargs...)

Keyword arguments

• sufficient_decrease=1e-4
• sufficient_curvature=0.999
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stop_when_stepsize_less=0.0: smallest stepsize when to stop (the last one before is taken)
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

WolfePowellLinesearchStepsize{R<:Real,TRM,VTM,P,T,I,TMSG} <: Linesearch

Do a backtracking line search to find a step size $α$ that fulfils the Wolfe conditions along a search direction $X$ starting from $p$. See WolfePowellLinesearch for the math details.

Fields

• sufficient_decrease::R, sufficient_curvature::R: two constants in the line search
• candidate_direction::T: a tangent vector at the point $p$ on the manifold $\mathcal{M}$
• candidate_point::P: a point on the manifold $\mathcal{M}$ as temporary storage for candidates
• last_stepsize::R: the last computed stepsize
• max_stepsize::R: the largest stepsize allowed
• retraction_method::AbstractRetractionMethod: a retraction $\operatorname{retr}$ to use, see the section on retractions
• stop_when_stepsize_less::R: a safeguard to stop when the stepsize gets too small
• vector_transport_method::AbstractVectorTransportMethod: a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• stop_increasing_at_step::I: last step to increase the stepsize
• stop_decreasing_at_step::I: last step to decrease the stepsize
• messages::TMSG: a named tuple of StepsizeMessages about the stepsize search

Constructor

WolfePowellLinesearchStepsize(M::AbstractManifold; kwargs...)WolfePowellLinesearchStepsize(M::AbstractManifold, p; kwargs...)

Keyword arguments

• sufficient_decrease=1e-4
• sufficient_curvature=0.999
• p::P =rand(M): a point on the manifold $\mathcal{M}$ to store an interim result
• X::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$ as type of memory allocated for the candidate direction
• max_stepsize=max_stepsize(M): largest stepsize allowed here.
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stop_when_stepsize_less=0.0: smallest stepsize when to stop (the last one before is taken)
• stop_increasing_at_step=100: for the initial increase test (s_plus), stop after these many steps
• stop_decreasing_at_step=1000: for the initial decrease test (s_minus), stop after these many steps
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

_hz_bracket(
    hzls::HagerZhangLinesearchStepsize, M::AbstractManifold,
    mp::AbstractManoptProblem, p, η, c::Real, max_alpha::Real
)

Perform the bracketing phase of the Hager-Zhang linesearch starting from an initial stepsize c and not exceeding max_alpha.

Returns a tuple (i_a, i_b, f_eval, f_wolfe, f_early_maxstep) where i_a and i_b are the indices in the stored function evaluations such that the minimum is bracketed between triples[i_a].t and triples[i_b].t. f_eval is true if the maximum number of function evaluations has been reached during the bracketing phase. f_wolfe is true if the Wolfe conditions have been satisfied. f_early_maxstep is true if the maximum stepsize was reached early with negative slope and an improvement over the initial point.

_hz_evaluate_next_step(
    hzls::HagerZhangLinesearchStepsize, M::AbstractManifold,
    mp::AbstractManoptProblem, p, η, α::Real
)

Evaluate and store the next trial step for the Hager-Zhang linesearch.

Given the current iterate p, search direction η (in the tangent space at p), and a candidate step size α, this function

1. Retracts from p along η by step α into hzls.candidate_point (using hzls.retraction_method),
2. Vector-transports η to the candidate point into hzls.candidate_direction (using hzls.vector_transport_method),
3. Evaluates the objective and directional derivative via get_cost_and_differential(mp, hzls.candidate_point, hzls.candidate_direction),
4. Stores the resulting triple (α, f, df) in hzls.triples and increments hzls.last_evaluation_index.

This helper is side-effecting by design; it mutates hzls' internal storage.

Return value

By default return a tuple with three values:

• the index i_k::Int at which the new evaluation was stored.
• evaluation_limit_termination: true iff the maximum number of stored evaluations has been reached.
• wolfe_termination is true iff the (standard or approximate) Wolfe conditions are satisfied for the current candidate, according to hzls.current_mode.

Errors

Throws an error if called more often than the maximum number of allocated function evaluations (i.e. if hzls.triples would overflow).

_hz_secant2(
    hzls::HagerZhangLinesearchStepsize, M::AbstractManifold,
    mp::AbstractManoptProblem, p, η, i_a::Int, i_b::Int
)

Perform the secant-based update in the Hager-Zhang linesearch.

Computes a trial step using a secant interpolation of the bracketing endpoints. If the trial step is too close to an endpoint, falls back to a bisection step. Returns the updated bracketing indices and termination flags from the internal update routine.

Arguments

• hzls: linesearch state and storage.
• M: manifold for retractions and transports.
• mp: optimization problem providing cost and differential.
• p: current iterate.
• η: search direction in the tangent space at p.
• i_a, i_b: indices of the current bracketing interval in hzls.triples.

Return value

Returns (i_A, i_B, i_c, f_eval, f_wolfe) where

• i_A, i_B: indices bracketing the minimum after the update,
• i_c: index of the most recent evaluation (or -1 if the candidate was out of range),
• f_eval: true iff the evaluation limit has been reached,
• f_wolfe: true iff the Wolfe conditions are satisfied.

Steps (S1-S4)

• S1: compute a secant trial c from the current bracket and accept it unless too close to an endpoint (otherwise use a bisection step).
• S2/S3: if the trial becomes a new endpoint, perform an update from that side.
• S4: return the updated bracket and termination flags.

_hz_update(
    hzls::HagerZhangLinesearchStepsize, M::AbstractManifold,
    mp::AbstractManoptProblem, p, η, i_a::Int, i_b::Int, c::Real
)

Perform an update procedure of the Hager-Zhang linesearch given the current bracketing indices i_a and i_b and a candidate stepsize c.

Returns indices and termination information (i_A, i_B, i_c, f_eval, f_wolfe) where the minimum is now bracketed between alpha_values[i_A] and alpha_values[i_B]. Index i_c indicates the position at which evaluation of the candidate c was stored. If the candidate c is outside of the current bracket, the last index is returned as -1. f_eval is true if the maximum number of function evaluations has been reached. f_wolfe is true if the Wolfe conditions have been satisfied at the candidate i_c.

cubic_polynomial_argmin(a::UnivariateTriple, b::UnivariateTriple; warn::Bool = true)

Returns the local minimizer of the cubic polynomial $p$ with $p(a.t)=a.f$, $p(b.t)=b.f$, $p'(a.t)=a.df$, $p'(b.t)=b.df$.

Input

• a::UnivariateTriple{R}: triple of bracket value a
• b::UnivariateTriple{R}: triple of bracket value b

Keyword arguments

• warn::Bool: Boolean value if warnings should be displayed

cubic_stepsize_update_step(a::Real, b::Real, c::Real, τ::Real)

Step function to determine the stepsize update c described in [Hag89].

Input

• a::Real: first value of the bracket
• b::Real: second value of the bracket
• c::Real: update value
• τ::Real: minimal step tolerance

default_point_distance(::AbstractManifold, p)

The default Hager-Zhang guess for the distance between p and the solution to the optimization problem. The default is 0, which deactivates heuristic I0 (a). On each manifold with default_point_distance, you need to also implement default_vector_norm.

default_point_distance(::DefaultManifold, p)

Following [HZ06b], the expected distance to the optimal solution from p on DefaultManifold is the Inf norm of p.

default_vector_norm(M::AbstractManifold, p, X)

The norm used by the Hager-Zhang initial guess to measure the search direction X at p. There is no default implementation, because it is only needed on manifolds that also provide a specific default_point_distance method.

geometric_curvature_function(κ::Real, d::Real)

Compute the geometric curvature function $ζ_κ(d)$ used by the RDoG stepsize:

\[ζ_κ(d) = \begin{cases} 1, & \text{if } κ \ge 0,\\[4pt] \dfrac{\sqrt{|κ|}\,d}{\tanh(\sqrt{|κ|}\,d)}, & \text{if } κ < 0. \end{cases}\]

For small arguments, a Taylor approximation is used for numerical stability.

get_message(:stop_increasing, k::Int=-1, step::Real = NaN)

Display a message string for stopping the increase of the step size at iteration k and the step size step chosen instead.

get_message(:stepsize_less, k::Int=-1, step::Real = NaN, bound::Real = NaN)

Display a message string for the step size falling below its minimal bound at iteration k and the step size step used instead.

get_message(:non_descent_direction, k::Int)

Display a message string for a non-descent direction encountered at iteration k.

get_message(:stop_decreasing, k::Int=-1, step::Real = NaN)

Display a message string for stopping the decrease of the step size at iteration k and the step size step chosen instead.

get_message(a)

Given a certain structure a from within Manopt.jl, retrieve its last message of information, e.g. warnings from a step size. If no message is available, an empty string is returned.

get_message(:stepsize_exceeds, k::Int, step::Real = NaN, bound::Real = NaN)

Display a message string for a stepsize exceeding a certain bound at iteration k and the step size step chosen instead.

get_message(s::Symbol, args...)

For a certain set of symbols s, this message function turns them into human readable strings. The arguments usually contain an iteration number k or bounds to communicate to the user.

get_univariate_triple!(mp::AbstractManoptProblem, cbls::CubicBracketingLinesearchStepsize, p, η, t::Real)

Get the UnivariateTriple of the problem mp related to the step with stepsize $t$ from $p$ in direction $η$.

Input

• mp::AbstractManoptProblem
• cbls::CubicBracketingLinesearchStepsize: containing retraction_method, vector_transport and the temporary candidate_point and candidate_direction
• p: point in the manifold of mp
• η: search direction at p
• t::Real: step size

reset_messages!(messages::NamedTuple)

Given a named tuple of StepsizeMessages, reset all messages to default values, i.e. at_iteration = -1, bound = 0, value = 0.

secant(a::UnivariateTriple, b::UnivariateTriple)

Returns the extremum of the quadratic polynomial $p$ with $p'(a.t)=a.df$, $p'(b.t)=b.df$.

The result is algebraically equivalent to (a.t * b.df - b.t * a.df) / (b.df - a.df) but the used formula is more numerically stable.

Input

• a::UnivariateTriple{R}: triple of bracket value a
• b::UnivariateTriple{R}: triple of bracket value b

set_message!(messages::NamedTuple, key::Symbol; at=nothing, bound=nothing, value=nothing)

Given a named tuple of StepsizeMessages, set the message identified by key to the provided values, i.e. if they are not nothing.

set_message!(message::StepsizeMessage, at=nothing, bound=nothing, value=nothing)

Set the fields of a single StepsizeMessage to the provided values, i.e. to those that are not nothing.

update_bracket(a::UnivariateTriple, b::UnivariateTriple, c::UnivariateTriple)

Updates bracket w.r.t. the bracketing strategy in [Hag89] (R3) - (R5).

Input

• a::UnivariateTriple{R}: triple of bracket value a
• b::UnivariateTriple{R}: triple of bracket value b
• c::UnivariateTriple{R}: triple of update value