Conjugate gradient descent

conjugate_gradient_descent(M, f, grad_f, p=rand(M))
conjugate_gradient_descent!(M, f, grad_f, p)
conjugate_gradient_descent(M, gradient_objective, p)
conjugate_gradient_descent!(M, gradient_objective, p; kwargs...)

perform a conjugate gradient based descent

\[p_{k+1} = \operatorname{retr}_{p_k} \bigl( s_kδ_k \bigr),\]

where $\operatorname{retr}$ denotes a retraction on the Manifold M and one can employ different rules to update the descent direction $δ_k$ based on the last direction $δ_{k-1}$ and both gradients $\operatorname{grad}f(p_k)$, $\operatorname{grad} f(p_{k-1})$. The Stepsize $s_k$ may be determined by a Linesearch.

Alternatively to f and grad_f you can provide the AbstractManifoldFirstOrderObjective gradient_objective directly.

Available update rules are SteepestDescentCoefficient, which yields a gradient_descent, ConjugateDescentCoefficient (the default), DaiYuanCoefficient, FletcherReevesCoefficient, HagerZhangCoefficient, HestenesStiefelCoefficient, LiuStoreyCoefficient, and PolakRibiereCoefficient. These can all be combined with a ConjugateGradientBealeRestartRule rule.

They all compute $β_k$ such that this algorithm updates the search direction as

\[δ_k = -\operatorname{grad}f(p_k) + β_k \mathcal T_{p_k←p_{k-1}} δ_{k-1}\]

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
• f: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v
• grad_f: the (Riemannian) gradient $\operatorname{grad}f: \mathcal{M} → T\mathcal{M}$ of f as a function (M, p) -> X or a function (M, X, p) -> X computing X in-place
• p::P: a point on the manifold $\mathcal{M}$

Keyword arguments

• callbacks::D = Dict{Symbol,Function}(): provided callback functions given either as a single function (symbol, problem, state, k) called in every hook or as a (vector of) pairs :hook => function, which are processed by process_callbacks_arg. As key you can either pass single symbol or an array of symbols to indicate a callback should be added in multiple places
• coefficient::DirectionUpdateRule=ConjugateDescentCoefficient(): rule to compute the descent direction update coefficient $β_k$, as a functor, where the resulting function maps are (amp, cgs, k) -> β with amp an AbstractManoptProblem, cgs is the ConjugateGradientDescentState, and k is the current iteration.
• differential = missing: specify a specific function to evaluate the differential. By default, $Df(p)[X] = ⟨\operatorname{grad}f(p),X⟩$ is used
• evaluation::AbstractEvaluationType=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating their result (AllocatingEvaluation) or whether they modify their input argument to return the result therein (InplaceEvaluation). Since usually the first argument is the manifold, the modified argument is the second.
• initial_gradient::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$ to specify the representation of a tangent vector
• restart_condition::AbstractRestartCondition=RestartOnNonDescent(): rule when the algorithm should restart, i.e. use the negative gradient instead of the computed direction, as a functor where the resulting function maps are (amp, cgs, k) -> corr::Bool with amp an AbstractManoptProblem, cgs is the ConjugateGradientDescentState, and k is the current iteration.
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize::Stepsize=ArmijoLinesearch(): a functor inheriting from Stepsize to determine a step size
• stopping_criterion::StoppingCriterion=StopAfterIteration(500)|StopWhenGradientNormLess(1e-8): a functor indicating that the stopping criterion is fulfilled
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

If you provide the ManifoldFirstOrderObjective directly, the evaluation= keyword is ignored. The decorations are still applied to the objective.

All other keyword arguments are passed to decorate_state! for state decorators or decorate_objective! for objective decorators, respectively.

Output

The obtained approximate minimizer $p^*$. To obtain the whole final state of the solver, see get_solver_return for details, especially the return_state= keyword.

conjugate_gradient_descent(M, f, grad_f, p=rand(M))
conjugate_gradient_descent!(M, f, grad_f, p)
conjugate_gradient_descent(M, gradient_objective, p)
conjugate_gradient_descent!(M, gradient_objective, p; kwargs...)

perform a conjugate gradient based descent

\[p_{k+1} = \operatorname{retr}_{p_k} \bigl( s_kδ_k \bigr),\]

where $\operatorname{retr}$ denotes a retraction on the Manifold M and one can employ different rules to update the descent direction $δ_k$ based on the last direction $δ_{k-1}$ and both gradients $\operatorname{grad}f(p_k)$, $\operatorname{grad} f(p_{k-1})$. The Stepsize $s_k$ may be determined by a Linesearch.

Alternatively to f and grad_f you can provide the AbstractManifoldFirstOrderObjective gradient_objective directly.

Available update rules are SteepestDescentCoefficient, which yields a gradient_descent, ConjugateDescentCoefficient (the default), DaiYuanCoefficient, FletcherReevesCoefficient, HagerZhangCoefficient, HestenesStiefelCoefficient, LiuStoreyCoefficient, and PolakRibiereCoefficient. These can all be combined with a ConjugateGradientBealeRestartRule rule.

They all compute $β_k$ such that this algorithm updates the search direction as

\[δ_k = -\operatorname{grad}f(p_k) + β_k \mathcal T_{p_k←p_{k-1}} δ_{k-1}\]

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
• f: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v
• grad_f: the (Riemannian) gradient $\operatorname{grad}f: \mathcal{M} → T\mathcal{M}$ of f as a function (M, p) -> X or a function (M, X, p) -> X computing X in-place
• p::P: a point on the manifold $\mathcal{M}$

Keyword arguments

• callbacks::D = Dict{Symbol,Function}(): provided callback functions given either as a single function (symbol, problem, state, k) called in every hook or as a (vector of) pairs :hook => function, which are processed by process_callbacks_arg. As key you can either pass single symbol or an array of symbols to indicate a callback should be added in multiple places
• coefficient::DirectionUpdateRule=ConjugateDescentCoefficient(): rule to compute the descent direction update coefficient $β_k$, as a functor, where the resulting function maps are (amp, cgs, k) -> β with amp an AbstractManoptProblem, cgs is the ConjugateGradientDescentState, and k is the current iteration.
• differential = missing: specify a specific function to evaluate the differential. By default, $Df(p)[X] = ⟨\operatorname{grad}f(p),X⟩$ is used
• evaluation::AbstractEvaluationType=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating their result (AllocatingEvaluation) or whether they modify their input argument to return the result therein (InplaceEvaluation). Since usually the first argument is the manifold, the modified argument is the second.
• initial_gradient::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$ to specify the representation of a tangent vector
• restart_condition::AbstractRestartCondition=RestartOnNonDescent(): rule when the algorithm should restart, i.e. use the negative gradient instead of the computed direction, as a functor where the resulting function maps are (amp, cgs, k) -> corr::Bool with amp an AbstractManoptProblem, cgs is the ConjugateGradientDescentState, and k is the current iteration.
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize::Stepsize=ArmijoLinesearch(): a functor inheriting from Stepsize to determine a step size
• stopping_criterion::StoppingCriterion=StopAfterIteration(500)|StopWhenGradientNormLess(1e-8): a functor indicating that the stopping criterion is fulfilled
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

If you provide the ManifoldFirstOrderObjective directly, the evaluation= keyword is ignored. The decorations are still applied to the objective.

All other keyword arguments are passed to decorate_state! for state decorators or decorate_objective! for objective decorators, respectively.

Output

The obtained approximate minimizer $p^*$. To obtain the whole final state of the solver, see get_solver_return for details, especially the return_state= keyword.

ConjugateGradientDescentState <: AbstractGradientSolverState

specify options for a conjugate gradient descent algorithm, that solves a DefaultManoptProblem.

Fields

• callbacks::D: provided callback functions given as a dictionary with symbols as keys
• p::P: a point on the manifold $\mathcal{M}$ storing the current iterate
• p_old: the previous iterate, stored to transport the direction δ to the new iterate
• X::T: a tangent vector at the point $p$ on the manifold $\mathcal{M}$
• δ: the current descent direction, also a tangent vector
• β: the current update coefficient, computed by the coefficient rule
• coefficient: function to determine the new β
• restart_condition: an AbstractRestartCondition to determine how to handle non-descent directions.
• stepsize::Stepsize: a functor inheriting from Stepsize to determine a step size
• stop::StoppingCriterion: a functor indicating that the stopping criterion is fulfilled
• 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

Constructor

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

where the last six fields can be set by their names as keyword (the field stop via the keyword stopping_criterion) and the X can be set to a tangent vector type using the keyword initial_gradient which defaults to zero_vector(M,p), and δ is initialized to a copy of this vector.

Keyword arguments

The following fields from above are keyword arguments

• initial_gradient::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$
• p::P =rand(M): a point on the manifold $\mathcal{M}$ to specify the initial value
• coefficient=ConjugateDescentCoefficient(): specify a CG coefficient, see also the ManifoldDefaultsFactory.
• restart_condition=RestartOnNonDescent(): specify a restart condition. It defaults to RestartOnNonDescent.
• stepsize::Stepsize=default_stepsize(M, ConjugateGradientDescentState; retraction_method=retraction_method): a functor inheriting from Stepsize to determine a step size
• stopping_criterion::StoppingCriterion=StopAfterIteration(500)|StopWhenGradientNormLess(1e-8): a functor indicating that the stopping criterion is fulfilled
• 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

See also

conjugate_gradient_descent, DefaultManoptProblem, ArmijoLinesearch

NeverRestart <: AbstractRestartCondition

A restart strategy that indicates to never restart.

RestartOnNonDescent <: AbstractRestartCondition

A restart strategy that restarts, whenever the search direction δ is not a descent direction, i.e. when

\[ ⟨\operatorname{grad}f(p), δ⟩ ≥ 0,\]

at the current iterate $p$.

RestartOnNonSufficientDescent <: AbstractRestartCondition

A restart strategy that indicates to restart whenever the search direction δ is not a sufficient descent direction, i.e. when

\[ ⟨\operatorname{grad}f(p), δ⟩ > - κ \lVert \operatorname{grad}f(p) \rVert^2,\]

at the current iterate $p$.

Fields

• κ: the sufficient decrease factor

Constructor

RestartOnNonSufficientDescent(κ::Real)

ConjugateDescentCoefficient()
ConjugateDescentCoefficient(M::AbstractManifold)

Compute the (classical) conjugate gradient coefficient based on [Fle87] adapted to manifolds

Denote the last iterate and gradient by $p_k,X_k$, the current iterate and gradient by $p_{k+1}, X_{k+1}$, respectively, as well as the last update direction by $δ_k$.

Then the coefficient reads

\[β_k = \frac{\mathrm{D}_{t}f(p_{k+1})[X_{k+1}]}{\mathrm{D}_{t}f(p_k)[-δ_k]} = \frac{\lVert X_{k+1} \rVert_{p_{k+1}}^2}{⟨-δ_k,X_k⟩_{p_k}}\]

The second one is the one usually stated, while the first one avoids using the metric inner. The first one is implemented here, but falls back to calling inner if there is no dedicated differential available.

ConjugateGradientBealeRestart(direction_update::Union{DirectionUpdateRule,ManifoldDefaultsFactory}; kwargs...)
ConjugateGradientBealeRestart(M::AbstractManifold, direction_update::Union{DirectionUpdateRule,ManifoldDefaultsFactory}; kwargs...)

Compute a conjugate gradient coefficient with a potential restart, when two directions are nearly orthogonal. See [HZ06a, page 12] (in the preprint, page 46 in Journal page numbers). This method is named after E. Beale from his proceedings paper in 1972 [Bea72]. This method acts as a decorator to any existing DirectionUpdateRule direction_update.

Denote the last iterate and gradient by $p_k,X_k$, the current iterate and gradient by $p_{k+1}, X_{k+1}$, respectively, as well as the last update direction by $δ_k$.

Then a restart is performed, hence $β_k = 0$ returned if

\[ \frac{⟨X_{k+1}, \mathcal T_{p_{k+1}←p_k}X_k⟩}{\lVert X_{k+1} \rVert_{p_{k+1}}} > ε,\]

where $ε$ is the threshold, which is set by default to 0.2, see [Pow77]

Input

• direction_update: a DirectionUpdateRule or a corresponding ManifoldDefaultsFactory to produce such a rule.

Keyword arguments

• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• threshold=0.2

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

Computes an update coefficient for the conjugate_gradient_descent algorithm based on [DY99] adapted to Riemannian manifolds.

Denote the last iterate and gradient by $p_k,X_k$, the current iterate and gradient by $p_{k+1}, X_{k+1}$, respectively, as well as the last update direction by $δ_k$.

Let $ν_k = X_{k+1} - \mathcal T_{p_{k+1}←p_k}X_k$, where $\mathcal T_{⋅←⋅}$ denotes a vector transport.

Then the coefficient reads

\[β_k = \frac{\mathrm{D}_{t}f(p_{k+1})[X_{k+1}]}{⟨\mathcal T_{p_{k+1}←p_k}δ_k,ν_k⟩_{p_{k+1}}} = \frac{\lVert X_{k+1} \rVert_{p_{k+1}}^2}{⟨\mathcal T_{p_{k+1}←p_k}δ_k, ν_k⟩_{p_{k+1}}}\]

The second one is the one usually stated, while the first one avoids using the metric inner. The first one is implemented here, but falls back to calling inner if there is no dedicated differential available.

Keyword arguments

• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

FletcherReevesCoefficient()
FletcherReevesCoefficient(M::AbstractManifold)

Computes an update coefficient for the conjugate_gradient_descent algorithm based on [FR64] adapted to manifolds

Denote the last iterate and gradient by $p_k,X_k$, the current iterate and gradient by $p_{k+1}, X_{k+1}$, respectively, as well as the last update direction by $δ_k$.

Then the coefficient reads

\[β_k = \frac{\mathrm{D}_{t}f(p_{k+1})[X_{k+1}]}{\mathrm{D}_{t}f(p_k)[X_k]} = \frac{\lVert X_{k+1} \rVert_{p_{k+1}}^2}{\lVert X_k \rVert_{p_k}^2}\]

The second one is the one usually stated, while the first one avoids using the metric inner. The first one is implemented here, but falls back to calling inner if there is no dedicated differential available.

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

Computes an update coefficient for the conjugate_gradient_descent algorithm based on [HZ05] adapted to manifolds

Denote the last iterate and gradient by $p_k,X_k$, the current iterate and gradient by $p_{k+1}, X_{k+1}$, respectively, as well as the last update direction by $δ_k$.

Let $ν_k = X_{k+1} - \mathcal T_{p_{k+1}←p_k}X_k$, where $\mathcal T_{⋅←⋅}$ denotes a vector transport.

Then the coefficient reads

\[β_k = \Bigl⟨ν_k - \frac{2\lVert ν_k \rVert_{p_{k+1}}^2}{⟨\mathcal T_{p_{k+1}←p_k}δ_k, ν_k⟩_{p_{k+1}}} \mathcal T_{p_{k+1}←p_k}δ_k, \frac{X_{k+1}}{⟨\mathcal T_{p_{k+1}←p_k}δ_k, ν_k⟩_{p_{k+1}}} \Bigr⟩_{p_{k+1}}.\]

This method includes a numerical stability proposed by those authors.

Keyword arguments

• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• denom_threshold::Real=1e-10: a threshold to avoid numerical instabilities when the inner product of δ and the difference of gradients is close to zero.

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

Computes an update coefficient for the conjugate_gradient_descent algorithm based on [HS52] adapted to manifolds

Denote the last iterate and gradient by $p_k,X_k$, the current iterate and gradient by $p_{k+1}, X_{k+1}$, respectively, as well as the last update direction by $δ_k$.

Let $ν_k = X_{k+1} - \mathcal T_{p_{k+1}←p_k}X_k$, where $\mathcal T_{⋅←⋅}$ denotes a vector transport.

Then the coefficient reads

\[\begin{aligned} β_k &= \frac{\mathrm{D}_{t}f(p_{k+1})[ν_k]}{\mathrm{D}_{t}f(p_{k+1})[\mathcal T_{p_{k+1}←p_k}δ_k] - \mathrm{D}_{t}f(p_k)[δ_k]} \\&= \frac{⟨X_{k+1},ν_k⟩_{p_{k+1}}}{⟨\mathcal T_{p_{k+1}←p_k}δ_k,X_{k+1}⟩_{p_{k+1}} - ⟨δ_k,X_k⟩_{p_{k}}} \\&= \frac{⟨X_{k+1},ν_k⟩_{p_{k+1}}}{⟨\mathcal T_{p_{k+1}←p_k}δ_k,ν_k⟩_{p_{k+1}}}, \end{aligned}\]

The third one is the one usually stated, while the first one avoids using the metric inner. The first one is implemented here, but falls back to calling inner if there is no dedicated differential available. The rule employs the nonnegative variant $β_k^{+} = \max(0, β_k)$ of this coefficient.

Keyword arguments

• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

HybridCoefficient(coefficients::Union{DirectionUpdateRule,ManifoldDefaultsFactory}...; kwargs...)
HybridCoefficient(M::AbstractManifold, coefficients::Union{DirectionUpdateRule,ManifoldDefaultsFactory}...; kwargs...)

Computes a hybrid update coefficient for the conjugate_gradient_descent.

Given coefficients $β_i$ for $i = 1,...,m$, a lower bound coefficient $β_0$, and a scalar factor $σ$ for the lower bound, this coefficient computes

\[β_k = \max\{σ * β_0, \min(β_1, …, β_m)\}\]

This includes the HS-DY and FR-PRP hybrid parameters introduced in [SI20] and [SI21]

Input

• coefficients... : CG coefficients of type DirectionUpdateRule or a corresponding ManifoldDefaultsFactory to produce such a rule, of which the minimum is taken in the

hybrid rule

Keyword arguments

• lower_bound=SteepestDescentCoefficient() : a lower bound DirectionUpdateRule or a corresponding

ManifoldDefaultsFactory for the resulting value of β

• lower_bound_scale=1.0 : a scalar to multiply the lower bound coefficient by.

Examples

The FR-PRP parameter reads

\[β_k^{\mathrm{FR-PRP}} = \max\{0, \min(β_k^{FR}, β_k^{PRP})\}\]

and can be implemented using

HybridCoefficient(FletcherReevesCoefficient(),PolakRibiereCoefficient())

The HS-DY parameter with parameter 0<σ<1 reads

\[β_k^{\mathrm{HS-DY}} = \max\bigl(-σ β_k^{DY}, \min(β_k^{HS}, β_k^{DY})\bigr)\]

and can be implemented using HybridCoefficient(HestenesStiefelCoefficient(),DaiYuanCoefficient(); lower_bound =DaiYuanCoefficient(), lower_bound_scale = -σ)

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

Computes an update coefficient for the conjugate_gradient_descent algorithm based on [LS91] adapted to manifolds

Denote the last iterate and gradient by $p_k,X_k$, the current iterate and gradient by $p_{k+1}, X_{k+1}$, respectively, as well as the last update direction by $δ_k$.

Let $ν_k = X_{k+1} - \mathcal T_{p_{k+1}←p_k}X_k$, where $\mathcal T_{⋅←⋅}$ denotes a vector transport.

Then the coefficient reads

\[β_k = - \frac{\mathrm{D}_{t}f(p_{k+1})[ν_k]}{\mathrm{D}_{t}f(p_k)[δ_k]} = - \frac{⟨X_{k+1},ν_k⟩_{p_{k+1}}}{⟨δ_k,X_k⟩_{p_k}}.\]

The second one is the one usually stated, while the first one avoids using the metric inner. The first one is implemented here, but falls back to calling inner if there is no dedicated differential available.

Keyword arguments

• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

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

Computes an update coefficient for the conjugate_gradient_descent algorithm based on [PR69] adapted to Riemannian manifolds.

Denote the last iterate and gradient by $p_k,X_k$, the current iterate and gradient by $p_{k+1}, X_{k+1}$, respectively, as well as the last update direction by $δ_k$.

Let $ν_k = X_{k+1} - \mathcal T_{p_{k+1}←p_k}X_k$, where $\mathcal T_{⋅←⋅}$ denotes a vector transport.

Then the coefficient reads

\[β_k = \frac{\mathrm{D}_{t}f(p_{k+1})[ν_k]}{\mathrm{D}_{t}f(p_k)[X_k]} = \frac{⟨X_{k+1},ν_k⟩_{p_{k+1}}}{\lVert X_k \rVert_{{p_k}}^2}.\]

The second one is the one usually stated, while the first one avoids using the metric inner. The first one is implemented here, but falls back to calling inner if there is no dedicated differential available. The rule employs the nonnegative variant $β_k^{+} = \max(0, β_k)$ of this coefficient.

Keyword arguments

• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

SteepestDescentCoefficient()
SteepestDescentCoefficient(M::AbstractManifold)

Computes an update coefficient for the conjugate_gradient_descent algorithm so that it falls back to a gradient_descent method, that is

\[β_k = 0\]

update_storage!(dur::DirectionUpdateRuleStorage, amp::AbstractManoptProblem, s::AbstractManoptSolverState)

Update the storage of a wrapped DirectionUpdateRule, and the storages of the rules it wraps, to the values currently given in s.

ConjugateDescentCoefficientRule <: DirectionUpdateRule

A functor (problem, state, k) -> β_k to compute the conjugate gradient update coefficient adapted to manifolds

See also conjugate_gradient_descent

Constructor

ConjugateDescentCoefficientRule()

Construct the conjugate descent coefficient update rule, a new storage is created by default.

See also

ConjugateDescentCoefficient, conjugate_gradient_descent

ConjugateGradientBealeRestartRule <: DirectionUpdateRule

A functor (problem, state, k) -> β_k to compute the conjugate gradient update coefficient based on a restart idea of [Bea72], following [HZ06a, page 12] adapted to manifolds.

Fields

• direction_update::DirectionUpdateRule: the actual rule, that is restarted
• threshold::Real: a threshold for the restart check.
• vector_transport_method::AbstractVectorTransportMethod: a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

Constructor

ConjugateGradientBealeRestartRule(    direction_update::Union{DirectionUpdateRule,ManifoldDefaultsFactory};    kwargs...)ConjugateGradientBealeRestartRule(    M::AbstractManifold=DefaultManifold(),    direction_update::Union{DirectionUpdateRule,ManifoldDefaultsFactory};    kwargs...)

Construct the Beale restart coefficient update rule adapted to manifolds.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$ If this is not provided, the DefaultManifold() from ManifoldsBase.jl is used.
• direction_update: a DirectionUpdateRule or a corresponding ManifoldDefaultsFactory to produce such a rule.

Keyword arguments

• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• threshold=0.2

See also

ConjugateGradientBealeRestart, conjugate_gradient_descent

DaiYuanCoefficientRule <: DirectionUpdateRule

A functor (problem, state, k) -> β_k to compute the conjugate gradient update coefficient based on [DY99] adapted to manifolds

Fields

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

Constructor

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

Construct the Dai—Yuan coefficient update rule.

Keyword arguments

• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

See also

DaiYuanCoefficient, conjugate_gradient_descent

FletcherReevesCoefficientRule <: DirectionUpdateRule

A functor (problem, state, k) -> β_k to compute the conjugate gradient update coefficient based on [FR64] adapted to manifolds

Constructor

FletcherReevesCoefficientRule()

Construct the Fletcher—Reeves coefficient update rule.

See also

FletcherReevesCoefficient, conjugate_gradient_descent

HagerZhangCoefficientRule <: DirectionUpdateRule

A functor (problem, state, k) -> β_k to compute the conjugate gradient update coefficient based on [HZ05] adapted to manifolds

Fields

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

Constructor

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

Construct the Hager-Zhang coefficient update rule based on [HZ05] adapted to manifolds.

Keyword arguments

• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• denom_threshold::Real=1e-10: a threshold to avoid numerical instabilities when the inner product of δ and the difference of gradients is close to zero.

See also

HagerZhangCoefficient, conjugate_gradient_descent

HestenesStiefelCoefficientRule <: DirectionUpdateRule

A functor (problem, state, k) -> β_k to compute the conjugate gradient update coefficient based on [HS52] adapted to manifolds

Fields

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

Constructor

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

Construct the Hestenes-Stiefel coefficient update rule based on [HS52] adapted to manifolds.

Keyword arguments

• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

See also

HestenesStiefelCoefficient, conjugate_gradient_descent

HybridCoefficientRule <: DirectionUpdateRule

A functor (problem, state, k) -> β_k to compute hybrid conjugate gradient update coefficients

Fields

• coefficients::Vector{<:DirectionUpdateRule}: a vector containing storage wrappers of the CG coefficients of which the minimum is taken
• lower_bound::DirectionUpdateRuleStorage: storage wrapper of lower bound CG coefficient
• lower_bound_scale::Real: scalar the lower bound is multiplied with

Constructor

HybridCoefficientRule(    M::AbstractManifold, coefficients::Union{DirectionUpdateRule,ManifoldDefaultsFactory}...;    lower_bound::Union{DirectionUpdateRule,ManifoldDefaultsFactory}=SteepestDescentCoefficient(),    lower_bound_scale::Real=1.0)

Construct the hybrid coefficient update rule.

See also

HybridCoefficient, conjugate_gradient_descent

LiuStoreyCoefficientRule <: DirectionUpdateRule

A functor (problem, state, k) -> β_k to compute the conjugate gradient update coefficient based on [LS91] adapted to manifolds

Fields

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

Constructor

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

Construct the Liu-Storey coefficient update rule based on [LS91] adapted to manifolds.

Keyword arguments

• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

See also

LiuStoreyCoefficient, conjugate_gradient_descent

PolakRibiereCoefficientRule <: DirectionUpdateRule

A functor (problem, state, k) -> β_k to compute the conjugate gradient update coefficient based on [PR69] adapted to manifolds

Fields

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

Constructor

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

Construct the Polak-Ribière coefficient update rule based on [PR69] adapted to manifolds.

Keyword arguments

• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

See also

PolakRibiereCoefficient, conjugate_gradient_descent

SteepestDescentCoefficientRule <: DirectionUpdateRule

A functor (problem, state, k) -> β_k to compute the conjugate gradient update coefficient to obtain the steepest direction, that is $β_k=0$.

Constructor

SteepestDescentCoefficientRule()

Construct the steepest descent coefficient update rule.

See also

SteepestDescentCoefficient, conjugate_gradient_descent