Conjugate residual solver in a Tangent space

conjugate_residual(TpM::TangentSpace, A, b, X=zero_vector(TpM))
conjugate_residual(TpM::TangentSpace, slso::SymmetricLinearSystemObjective, X=zero_vector(TpM))
conjugate_residual!(TpM::TangentSpace, A, b, X)
conjugate_residual!(TpM::TangentSpace, slso::SymmetricLinearSystemObjective, X)

Compute the solution of $\mathcal A(p)[X] + b(p) = 0_p$, where

• $\mathcal A$ is a linear, symmetric operator on $T_{p}\mathcal M$
• $b$ is a vector field on the manifold
• $X ∈ T_{p}\mathcal M$ is a tangent vector
• $0_p$ is the zero vector $T_{p}\mathcal M$.

This implementation follows Algorithm 3 in [LY24] and is initalised with $X^{(0)}$ as the zero vector and

• the initial residual $r^{(0)} = -b(p) - \mathcal A(p)[X^{(0)}]$
• the initial conjugate direction $d^{(0)} = r^{(0)}$
• initialize $Y^{(0)} = \mathcal A(p)[X^{(0)}]$

performed the following steps at iteration $k=0,…$ until the stopping_criterion is fulfilled.

1. compute a step size $α_k = \displaystyle\frac{⟨ r^{(k)}, \mathcal A(p)[r^{(k)}] ⟩_p}{⟨ \mathcal A(p)[d^{(k)}], \mathcal A(p)[d^{(k)}] ⟩_p}$
2. do a step $X^{(k+1)} = X^{(k)} + α_kd^{(k)}$
3. update the residual $r^{(k+1)} = r^{(k)} + α_k Y^{(k)}$
4. compute $Z = \mathcal A(p)[r^{(k+1)}]$
5. Update the conjugate coefficient $β_k = \displaystyle\frac{⟨ r^{(k+1)}, \mathcal A(p)[r^{(k+1)}] ⟩_p}{⟨ r^{(k)}, \mathcal A(p)[r^{(k)}] ⟩_p}$
6. Update the conjugate direction $d^{(k+1)} = r^{(k+1)} + β_kd^{(k)}$
7. Update $Y^{(k+1)} = -Z + β_k Y^{(k)}$

Note that the right hand side of Step 7 is the same as evaluating $\mathcal A[d^{(k+1)}]$, but avoids the actual evaluation

Input

• TpM the TangentSpace as the domain
• A a symmetric linear operator on the tangent space (M, p, X) -> Y
• b a vector field on the tangent space (M, p) -> X
• X the initial tangent vector

Keyword arguments

• 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.
• stopping_criterion=StopAfterIteration(manifold_dimension(M)|StopWhenRelativeResidualLess(c,1e-8), where c is $\lVert b \rVert_{}$: a functor indicating that the stopping criterion is fulfilled

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_residual(TpM::TangentSpace, A, b, X=zero_vector(TpM))
conjugate_residual(TpM::TangentSpace, slso::SymmetricLinearSystemObjective, X=zero_vector(TpM))
conjugate_residual!(TpM::TangentSpace, A, b, X)
conjugate_residual!(TpM::TangentSpace, slso::SymmetricLinearSystemObjective, X)

Compute the solution of $\mathcal A(p)[X] + b(p) = 0_p$, where

• $\mathcal A$ is a linear, symmetric operator on $T_{p}\mathcal M$
• $b$ is a vector field on the manifold
• $X ∈ T_{p}\mathcal M$ is a tangent vector
• $0_p$ is the zero vector $T_{p}\mathcal M$.

This implementation follows Algorithm 3 in [LY24] and is initalised with $X^{(0)}$ as the zero vector and

• the initial residual $r^{(0)} = -b(p) - \mathcal A(p)[X^{(0)}]$
• the initial conjugate direction $d^{(0)} = r^{(0)}$
• initialize $Y^{(0)} = \mathcal A(p)[X^{(0)}]$

performed the following steps at iteration $k=0,…$ until the stopping_criterion is fulfilled.

1. compute a step size $α_k = \displaystyle\frac{⟨ r^{(k)}, \mathcal A(p)[r^{(k)}] ⟩_p}{⟨ \mathcal A(p)[d^{(k)}], \mathcal A(p)[d^{(k)}] ⟩_p}$
2. do a step $X^{(k+1)} = X^{(k)} + α_kd^{(k)}$
3. update the residual $r^{(k+1)} = r^{(k)} + α_k Y^{(k)}$
4. compute $Z = \mathcal A(p)[r^{(k+1)}]$
5. Update the conjugate coefficient $β_k = \displaystyle\frac{⟨ r^{(k+1)}, \mathcal A(p)[r^{(k+1)}] ⟩_p}{⟨ r^{(k)}, \mathcal A(p)[r^{(k)}] ⟩_p}$
6. Update the conjugate direction $d^{(k+1)} = r^{(k+1)} + β_kd^{(k)}$
7. Update $Y^{(k+1)} = -Z + β_k Y^{(k)}$

Note that the right hand side of Step 7 is the same as evaluating $\mathcal A[d^{(k+1)}]$, but avoids the actual evaluation

Input

• TpM the TangentSpace as the domain
• A a symmetric linear operator on the tangent space (M, p, X) -> Y
• b a vector field on the tangent space (M, p) -> X
• X the initial tangent vector

Keyword arguments

• 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.
• stopping_criterion=StopAfterIteration(manifold_dimension(M)|StopWhenRelativeResidualLess(c,1e-8), where c is $\lVert b \rVert_{}$: a functor indicating that the stopping criterion is fulfilled

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.

ConjugateResidualState{T,R,TStop<:StoppingCriterion} <: AbstractManoptSolverState

A state for the conjugate_residual solver.

Fields

• X::T: the iterate
• r::T: the residual $r = -b(p) - \mathcal A(p)[X]$
• d::T: the conjugate direction
• Ar::T, Ad::T: storages for $\mathcal A(p)[d]$, $\mathcal A(p)[r]$
• rAr::R: internal field for storing $⟨ r, \mathcal A(p)[r] ⟩$
• α::R: a step length
• β::R: the conjugate coefficient
• stop::StoppingCriterion: a functor indicating that the stopping criterion is fulfilled

Constructor

ConjugateResidualState(TpM::TangentSpace,slso::SymmetricLinearSystemObjective; kwargs...)

Initialise the state with default values.

Keyword arguments

• r=-get_gradient(TpM, slso, X)
• d=copy(TpM, r)
• Ar=get_hessian(TpM, slso, X, r)
• Ad=copy(TpM, Ar)
• α::R=0.0
• β::R=0.0
• stopping_criterion=StopAfterIteration(manifold_dimension(M))|StopWhenGradientNormLess(1e-8): a functor indicating that the stopping criterion is fulfilled
• X=zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal M$

See also

conjugate_residual

SymmetricLinearSystemObjective{E<:AbstractEvaluationType,TA,T} <: AbstractManifoldObjective{E}

Model the objective

\[f(X) = \frac{1}{2} \lVert \mathcal A[X] + b \rVert_{p}^2,\qquad X ∈ T_{p}\mathcal M,\]

defined on the tangent space $T_{p}\mathcal M$ at $p$ on the manifold $\mathcal M$.

In other words this is an objective to solve $\mathcal A = -b(p)$ for some linear symmetric operator and a vector function. Note the minus on the right hand side, which makes this objective especially tailored for (iteratively) solving Newton-like equations.

Fields

• A!!: a symmetric, linear operator on the tangent space
• b!!: a gradient function

where A!! can work as an allocating operator (M, p, X) -> Y or an in-place one (M, Y, p, X) -> Y, and similarly b!! can either be a function (M, p) -> X or (M, X, p) -> X. The first variants allocate for the result, the second variants work in-place.

Constructor

SymmetricLinearSystemObjective(A, b; evaluation=AllocatingEvaluation())

Generate the objective specifying whether the two parts work allocating or in-place.

StopWhenRelativeResidualLess <: StoppingCriterion

Stop when re relative residual in the conjugate_residual is below a certain threshold, i.e.

\[\displaystyle\frac{\lVert r^{(k) \rVert_{}}{c} ≤ ε,\]

where $c = \lVert b \rVert_{}$ of the initial vector from the vector field in $\mathcal A(p)[X] + b(p) = 0_p$, from the conjugate_residual

Fields

• at_iteration::Int: an integer indicating at which the stopping criterion last indicted to stop, which might also be before the solver started (0). Any negative value indicates that this was not yet the case;
• c: the initial norm
• ε: the threshold
• norm_rk: the last computed norm of the residual

Constructor

StopWhenRelativeResidualLess(c, ε; norm_r = 2*c*ε)

Initialise the stopping criterion.

get_b(TpM::TangentSpace, slso::SymmetricLinearSystemObjective)

evaluate the stored value for computing the right hand side $b$ in $\mathcal A=-b$.