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(x_k)$,$\operatorname{grad} f(x_{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 SteepestDescentCoefficientRule, which yields a gradient_descent, ConjugateDescentCoefficient (the default), DaiYuanCoefficientRule, 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 \delta_{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_{p}\mathcal M$ of f as a function (M, p) -> X or a function (M, X, p) -> X computing X in-place
• p: a point on the manifold $\mathcal M$

Keyword arguments

• 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 iterate.
• differential=nothing: specify a specific function to evaluate the differential. By default, $Df(p)[X] = ⟨\operatorname{grad}f(p),X⟩$. is used
• evaluation=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating its 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.
• retraction_method=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize=ArmijoLinesearch(): a functor inheriting from Stepsize to determine a step size
• stopping_criterion=StopAfterIteration(500)|StopWhenGradientNormLess(1e-8): a functor indicating that the stopping criterion is fulfilled
• vector_transport_method=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.

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(x_k)$,$\operatorname{grad} f(x_{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 SteepestDescentCoefficientRule, which yields a gradient_descent, ConjugateDescentCoefficient (the default), DaiYuanCoefficientRule, 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 \delta_{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_{p}\mathcal M$ of f as a function (M, p) -> X or a function (M, X, p) -> X computing X in-place
• p: a point on the manifold $\mathcal M$

Keyword arguments

• 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 iterate.
• differential=nothing: specify a specific function to evaluate the differential. By default, $Df(p)[X] = ⟨\operatorname{grad}f(p),X⟩$. is used
• evaluation=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating its 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.
• retraction_method=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize=ArmijoLinesearch(): a functor inheriting from Stepsize to determine a step size
• stopping_criterion=StopAfterIteration(500)|StopWhenGradientNormLess(1e-8): a functor indicating that the stopping criterion is fulfilled
• vector_transport_method=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.

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.

ConjugateGradientState <: AbstractGradientSolverState

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

Fields

• p::P: a point on the manifold $\mathcal M$ storing the current 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 rule, see .
• coefficient: function to determine the new β
• 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::AbstractVectorTransportMethodP: a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

Constructor

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

where the last five fields can be set by their names as keyword 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 <re keyword arguments

• initial_gradient=zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal M$
• p=rand(M): a point on the manifold $\mathcal M$ to specify the initial value
• coefficient=[ConjugateDescentCoefficient](@ref)(): specify a CG coefficient, see also the [ManifoldDefaultsFactory`](@ref).
• stepsize=default_stepsize(M, ConjugateGradientDescentState; retraction_method=retraction_method): a functor inheriting from Stepsize to determine a step size
• stopping_criterion=StopAfterIteration(500)|StopWhenGradientNormLess(1e-8)): a functor indicating that the stopping criterion is fulfilled
• retraction_method=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• vector_transport_method=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

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}_{}f(p_{k+1})[X_{k+1}]}{\mathrm{D}_{}f(p_k)[-δ_k]} = \frac{\lVert X_{k+1} \rVert_{p_{k+1}}^2}{⟨-δ_k,X_k⟩_{p_k}}\]

The second one it the one usually stated, while the first one avoids to use 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 [HZ06, 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 \rVert_{p_k}} > ε,\]

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=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}_{}f(p_{k+1})[X_{k+1}]}{⟨δ_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 it the one usually stated, while the first one avoids to use 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=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}_{}f(p_{k+1})[X_{k+1}]}{\mathrm{D}_{}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 it the one usually stated, while the first one avoids to use 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 [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$.

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=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

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}_{}f(p_{k+1})[ν_k]}{\mathrm{D}_{}f(p_{k+1})[\mathcal T_{p_{k+1}←p_k}δ_k] - \mathrm{D}_{}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 to use 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=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

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}_{}f(p_{k+1})[ν_k]}{\mathrm{D}_{}f(p_k)[δ_k]} = - \frac{⟨X_{k+1},ν_k⟩_{p_{k+1}}}{⟨δ_k,X_k⟩_{p_k}}.\]

The second one it the one usually stated, while the first one avoids to use 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=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}_{}f(p_{k+1})[ν_k]}{\mathrm{D}_{}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 to use 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=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 is falls back to a gradient_descent method, that is

\[β_k = 0\]

ConjugateGradientBealeRestartRule <: DirectionUpdateRule

A functor (problem, state, k) -> β_k to compute the conjugate gradient update coefficient based on a restart idea of [Bea72], following [HZ06, 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::AbstractVectorTransportMethodP: 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=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::AbstractVectorTransportMethodP: 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=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::AbstractVectorTransportMethodP: 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=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

See also

HagerZhangCoefficient, conjugate_gradient_descent

HestenesStiefelCoefficientRuleRule <: DirectionUpdateRule

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

Fields

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

Constructor

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

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

Keyword arguments

• vector_transport_method=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

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::AbstractVectorTransportMethodP: a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

Constructor

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

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

Keyword arguments

• vector_transport_method=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::AbstractVectorTransportMethodP: a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

Constructor

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

Construct the Dai—Yuan coefficient update rule.

Keyword arguments

• vector_transport_method=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