# Conjugate residual solver in a Tangent space

Manopt.conjugate_residualFunction
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

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.

source
Manopt.conjugate_residual!Function
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

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.

source

## State

Manopt.ConjugateResidualStateType
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

conjugate_residual

source

## Objective

Manopt.SymmetricLinearSystemObjectiveType
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.

source

Manopt.StopWhenRelativeResidualLessType
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.

Note

The initial norm of the vector field $c = \lVert b \rVert_{}$ that is stored internally is updated on initialisation, that is, if this stopping criterion is called with k<=0.

source

## Internal functions

Manopt.get_bFunction
get_b(TpM::TangentSpace, slso::SymmetricLinearSystemObjective)

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

source

## Literature

[LY24]
Z. Lai and A. Yoshise. Riemannian Interior Point Methods for Constrained Optimization on Manifolds. Journal of Optimization Theory and Applications 201, 433–469 (2024), arXiv:2203.09762.