Steihaug-Toint truncated conjugate gradient method

truncated_conjugate_gradient_descent(M, f, grad_f, p; kwargs...)
truncated_conjugate_gradient_descent(M, f, grad_f, p, X; kwargs...)
truncated_conjugate_gradient_descent(M, f, grad_f, Hess_f; kwargs...)
truncated_conjugate_gradient_descent(M, f, grad_f, Hess_f, p; kwargs...)
truncated_conjugate_gradient_descent(M, f, grad_f, Hess_f, p, X; kwargs...)
truncated_conjugate_gradient_descent(M, mho::ManifoldHessianObjective, p, X; kwargs...)
truncated_conjugate_gradient_descent(M, trmo::TrustRegionModelObjective, p, X; kwargs...)

solve the trust-region subproblem

\[\begin{align*} \operatorname*{arg\,min}_{Y ∈ T_p\mathcal{M}}&\ m_p(Y) = f(p) + ⟨\operatorname{grad}f(p), Y⟩_p + \frac{1}{2} ⟨\mathcal{H}_p[Y], Y⟩_p\\ \text{such that}& \ \lVert Y \rVert_p ≤ Δ \end{align*}\]

on a manifold M by using the Steihaug-Toint truncated conjugate-gradient (tCG) method. For a description of the algorithm and theorems offering convergence guarantees, see [ABG06, CGT00].

Input

• M: a manifold $\mathcal M$
• f: a cost function $f: \mathcal M → ℝ$ to minimize
• grad_f: the gradient $\operatorname{grad}f: \mathcal M → T\mathcal M$ of F
• Hess_f: (optional, cf. ApproxHessianFiniteDifference) the Hessian $\operatorname{Hess}f: T_p\mathcal M → T_p\mathcal M$, $X ↦ \operatorname{Hess}F(p)[X] = ∇_X\operatorname{grad}f(p)$
• p: a point on the manifold $p ∈ \mathcal M$
• X: an initial tangential vector $X ∈ T_p\mathcal M$

Instead of the three functions, you either provide a ManifoldHessianObjective mho which is then used to build the trust region model, or a TrustRegionModelObjective trmo directly.

Optional

• evaluation: (AllocatingEvaluation) specify whether the gradient and Hessian work by allocation (default) or InplaceEvaluation in place
• preconditioner: a preconditioner for the Hessian H
• θ: (1.0) 1+θ is the superlinear convergence target rate.
• κ: (0.1) the linear convergence target rate.
• randomize: set to true if the trust-region solve is initialized to a random tangent vector. This disables preconditioning.
• trust_region_radius: (injectivity_radius(M)/4) a trust-region radius
• project!: (copyto!) for numerical stability it is possible to project onto the tangent space after every iteration. By default this only copies instead.
• stopping_criterion: (StopAfterIteration(manifol_dimension(M)) |StopWhenResidualIsReducedByFactorOrPower(;κ=κ, θ=θ) |StopWhenCurvatureIsNegative() |StopWhenTrustRegionIsExceeded() |StopWhenModelIncreased()) a functor inheriting from StoppingCriterion indicating when to stop,

and the ones that are passed to decorate_state! for decorators.

Output

the obtained (approximate) minimizer $Y^*$, see get_solver_return for details

See also

trust_regions

truncated_conjugate_gradient_descent!(M, f, grad_f, Hess_f, p, X; kwargs...)
truncated_conjugate_gradient_descent!(M, f, grad_f, p, X; kwargs...)

solve the trust-region subproblem in place of X (and p).

Input

• M: a manifold $\mathcal M$
• f: a cost function $F: \mathcal M → ℝ$ to minimize
• grad_f: the gradient $\operatorname{grad}f: \mathcal M → T\mathcal M$ of f
• Hess_f: the Hessian $\operatorname{Hess}f(x): T_p\mathcal M → T_p\mathcal M$, $X ↦ \operatorname{Hess}f(p)[X]$
• p: a point on the manifold $p ∈ \mathcal M$
• X: an update tangential vector $X ∈ T_x\mathcal M$

For more details and all optional arguments, see truncated_conjugate_gradient_descent.

TruncatedConjugateGradientState <: AbstractHessianSolverState

describe the Steihaug-Toint truncated conjugate-gradient method, with

Fields

a default value is given in brackets if a parameter can be left out in initialization.

• Y: (zero_vector(M,p)) Current iterate, whose type is also used for the other, internal, tangent vector fields
• stop: a StoppingCriterion.
• X: the gradient $\operatorname{grad}f(p)$`
• δ: the conjugate gradient search direction
• θ: (1.0) 1+θ is the superlinear convergence target rate.
• κ: (0.1) the linear convergence target rate.
• trust_region_radius: (injectivity_radius(M)/4) the trust-region radius
• residual: the gradient of the model $m(Y)$
• randomize: (false)
• project!: (copyto!) for numerical stability it is possible to project onto the tangent space after every iteration. By default this only copies instead.

Internal fields

• Hδ, HY: temporary results of the Hessian applied to δ and Y, respectively.
• δHδ, YPδ, δPδ, YPδ: temporary inner products with Hδ and preconditioned inner products.
• z: the preconditioned residual
• z_r: inner product of the residual and z

Constructor

TruncatedConjugateGradientState(TpM::TangentSpace, Y=rand(TpM); kwargs...)

See also

truncated_conjugate_gradient_descent, trust_regions

StopWhenResidualIsReducedByFactorOrPower <: StoppingCriterion

A functor for testing if the norm of residual at the current iterate is reduced either by a power of 1+θ or by a factor κ compared to the norm of the initial residual. The criterion hence reads $\Vert r_k \Vert_p \leqq \Vert r_0 \Vert_p \min \bigl( \kappa, \Vert r_0 \Vert_p^θ \bigr)$.

Fields

• κ: the reduction factor
• θ: part of the reduction power
• reason: stores a reason of stopping if the stopping criterion has one be reached, see get_reason.

Constructor

StopWhenResidualIsReducedByFactorOrPower(; κ=0.1, θ=1.0)

Initialize the StopWhenResidualIsReducedByFactorOrPower functor to indicate to stop after the norm of the current residual is lesser than either the norm of the initial residual to the power of 1+θ or the norm of the initial residual times κ.

See also

truncated_conjugate_gradient_descent, trust_regions

StopWhenTrustRegionIsExceeded <: StoppingCriterion

A functor for testing if the norm of the next iterate in the Steihaug-Toint truncated conjugate gradient method is larger than the trust-region radius $θ \leq \Vert Y_{k}^{*} \Vert_p$ and to end the algorithm when the trust region has been left.

Fields

• reason: stores a reason of stopping if the stopping criterion has been reached, see get_reason.

Constructor

StopWhenTrustRegionIsExceeded()

initialize the StopWhenTrustRegionIsExceeded functor to indicate to stop after the norm of the next iterate is greater than the trust-region radius.

See also

truncated_conjugate_gradient_descent, trust_regions

StopWhenCurvatureIsNegative <: StoppingCriterion

A functor for testing if the curvature of the model is negative, $⟨δ_k, \operatorname{Hess}[F](\delta_k)⟩_p ≦ 0$. In this case, the model is not strictly convex, and the stepsize as computed does not yield a reduction of the model.

Fields

• reason: stores a reason of stopping if the stopping criterion has been reached, see get_reason.

Constructor

StopWhenCurvatureIsNegative()

See also

truncated_conjugate_gradient_descent, trust_regions

StopWhenModelIncreased <: StoppingCriterion

A functor for testing if the curvature of the model value increased.

Fields

• reason: stores a reason of stopping if the stopping criterion has been reached, see get_reason.

Constructor

StopWhenModelIncreased()

See also

truncated_conjugate_gradient_descent, trust_regions

update_stopping_criterion!(c::StopWhenResidualIsReducedByFactorOrPower, :ResidualPower, v)

Update the residual Power θ to v.

update_stopping_criterion!(c::StopWhenResidualIsReducedByFactorOrPower, :ResidualFactor, v)

Update the residual Factor κ to v.

TrustRegionModelObjective{O<:AbstractManifoldHessianObjective} <: AbstractManifoldSubObjective{O}

A trust region model of the form

\[ m(X) = f(p) + ⟨\operatorname{grad} f(p), X⟩_p + \frac{1}(2} ⟨\operatorname{Hess} f(p)[X], X⟩_p\]

Fields

• objective: an AbstractManifoldHessianObjective proving $f$, its gradient and Hessian

Constructors

TrustRegionModelObjective(objective)

with either an AbstractManifoldHessianObjective objective or an decorator containing such an objective