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 Absil, Baker, Gallivan, FoCM, 2007, Conn, Gould, Toint, 2000.

Input

See signatures above, you can leave out only the Hessian, the vector, the point and the vector, or all 3.

• 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 possivle 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.

• p – (rand(M) a point, where we use the tangent space to solve the trust-region subproblem
• 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 possivle to project onto the tangent space after every iteration. By default this only copies instead.

Internal (temporary) 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(M, p=rand(M), Y=zero_vector(M,p); 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, i.e. $\Vert r_k \Vert_x \leqq \Vert r_0 \Vert_{x} \ \min \left( \kappa, \Vert r_0 \Vert_{x}^{\theta} \right)$.

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 tcg method is larger than the trust-region radius, i.e. $\Vert Y_{k}^{*} \Vert_x ≧ trust_region_radius$. terminate 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, i.e. $\langle \delta_k, \operatorname{Hess}[F](\delta_k)\rangle_x \leqq 0$. In this case, the model is not strictly convex, and the stepsize as computed does not give 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