GitHub

The Riemannian trust regions solver

Minimize a function

\[\operatorname*{arg\,min}_{p ∈ \mathcal{M}}\ f(p)\]

by using the Riemannian trust-regions solver following [ABG06]. A model is built by lifting the objective at the $k$th iterate $p^{(k)}$ by locally mapping the cost function $f$ to the tangent space as $f_k: T_{p^{(k)}}\mathcal M → ℝ$ as $f_k(X) = f(\operatorname{retr}_{p^{(k)}}(X))$. The trust region sub problem is then defined as

\[\operatorname*{arg\,min}_{X ∈ T_{p^{(k)}}\mathcal M}\ m_k(X) \quad\text{such that}\ \lVert X \rVert_{p^{(k)}} ≤ Δ_k,\]

where

\[\begin{align*} m_k&: T_{p^{(k)}}\mathcal M → ℝ,\\ m_k(X) &= f(p^{(k)}) + ⟨\operatorname{grad} f(p^{(k)}), X⟩_{p^{(k)}} + \frac{1}{2}\langle \mathcal H_k(X),X⟩_{p^{(k)}}. \end{align*}\]

Here $Δ_k$ is the trust region radius, which is adapted in every iteration, and $\mathcal H_k$ is some symmetric linear operator that approximates the Hessian $\operatorname{Hess} f$ of $f$.

Interface

Manopt.trust_regions — Function
trust_regions(M, f, grad_f, Hess_f, p=rand(M); kwargs...)
trust_regions(M, f, grad_f, p=rand(M); kwargs...)
trust_regions(M, mho, p=rand(M); kwargs...)
trust_regions!(M, f, grad_f, Hess_f, p; kwargs...)
trust_regions!(M, f, grad_f, p; kwargs...)
trust_regions!(M, mho, p; kwargs...)

run the Riemannian trust-regions solver for optimization on manifolds to minimize f, see [ABG06, CGT00].

For the case that no Hessian is provided, the Hessian is computed using finite differences, see ApproxHessianFiniteDifference. For solving the inner trust-region subproblem of finding an update-vector, by default the truncated_conjugate_gradient_descent is used.

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\mathcal{M}$ of f as a function (M, p) -> X or a function (M, X, p) -> X computing X in-place
  • Hess_f: the (Riemannian) Hessian $\operatorname{Hess}f: T_{p}\mathcal{M} → T_{p}\mathcal{M}$ of f as a function (M, p, X) -> Y or a function (M, Y, p, X) -> Y computing Y in-place
  • p::P: a point on the manifold $\mathcal{M}$

the cost f and its gradient and Hessian might also be provided as a ManifoldHessianObjective mho

Keyword arguments

  • acceptance_rate=0.1: accept/reject threshold: if ρ (the performance ratio for the iterate) is larger than the acceptance rate ρ', the candidate is accepted. This value should be between $0$ and $\frac{1}{4}$
  • augmentation_threshold=0.75: trust-region augmentation threshold: if ρ is larger than this threshold and the subsolver solution reached the trust region boundary (for instance due to negative curvature), the radius is extended (augmented)
  • augmentation_factor=2.0: trust-region augmentation factor
  • callbacks::D = Dict{Symbol,Function}(): provided callback functions given either as a single function (symbol, problem, state, k) called in every hook or as a (vector of) pairs :hook => function, which are processed by process_callbacks_arg. As key you can either pass single symbol or an array of symbols to indicate a callback should be added in multiple places
  • evaluation::AbstractEvaluationType=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating their 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.
  • κ=0.1: the linear convergence target rate of the tCG method truncated_conjugate_gradient_descent, and is used in a stopping criterion therein
  • max_trust_region_radius=sqrt(manifold_dimension(M)): the maximum trust-region radius
  • preconditioner: a preconditioner for the Hessian H. This is either an allocating function (M, p, X) -> Y or an in-place function (M, Y, p, X) -> Y, see evaluation, and by default set to the identity.
  • project!=copyto!: for numerical stability it is possible to project onto the tangent space after every iteration. the function has to work inplace of Y, that is (M, Y, p, X) -> Y, where X and Y can be the same memory.
  • randomize=false: indicate whether the initial tangent vector for the subsolver is chosen at random or not. This disables preconditioning.
  • ρ_regularization=1e3: regularize the performance evaluation $ρ$ to avoid numerical inaccuracies.
  • reduction_factor=0.25: trust-region reduction factor
  • reduction_threshold=0.1: trust-region reduction threshold: if ρ is below this threshold, the trust region radius is reduced by reduction_factor.
  • retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
  • σ=randomize ? 1e-3 : 0.0: Gaussian standard deviation when creating the random initial tangent vector; a value of 0 disables the randomized (Cauchy point) mode
  • stopping_criterion::StoppingCriterion=StopAfterIteration(1000)|StopWhenGradientNormLess(1e-6): a functor indicating that the stopping criterion is fulfilled
  • sub_kwargs = (;): a named tuple of keyword arguments that are passed to decorate_objective! of the sub solver's objective, the decorate_state! of the sub solver's state, and the sub state constructor itself.
  • sub_stopping_criterion::StoppingCriterion=( see truncated_conjugate_gradient_descent): a functor indicating that the stopping criterion is fulfilled
  • sub_objective: the sub objective to solve, by default the TrustRegionModelObjective of mho after the objective_type conversion, possibly decorated with sub_kwargs Note that this keyword has no effect if you set the sub_problem directly.
  • sub_problem::Union{AbstractManoptProblem, F} =DefaultManoptProblem(TangentSpace(M,p), sub_objective): specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
  • sub_state::Union{AbstractManoptSolverState,AbstractEvaluationType} =TruncatedConjugateGradientState: a state to specify the sub solver to use. For a closed form solution, this indicates the type of function. See also truncated_conjugate_gradient_descent for more details.
  • θ=1.0: the superlinear convergence target rate of $1+θ$ of the tCG-method truncated_conjugate_gradient_descent, and is used in a stopping criterion therein
  • trust_region_radius=max_trust_region_radius / 8: the initial trust-region radius

All other keyword arguments are passed to decorate_state! for state decorators or decorate_objective! for objective decorators, respectively.

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.

See also

truncated_conjugate_gradient_descent

source
Manopt.trust_regions! — Function
trust_regions(M, f, grad_f, Hess_f, p=rand(M); kwargs...)
trust_regions(M, f, grad_f, p=rand(M); kwargs...)
trust_regions(M, mho, p=rand(M); kwargs...)
trust_regions!(M, f, grad_f, Hess_f, p; kwargs...)
trust_regions!(M, f, grad_f, p; kwargs...)
trust_regions!(M, mho, p; kwargs...)

run the Riemannian trust-regions solver for optimization on manifolds to minimize f, see [ABG06, CGT00].

For the case that no Hessian is provided, the Hessian is computed using finite differences, see ApproxHessianFiniteDifference. For solving the inner trust-region subproblem of finding an update-vector, by default the truncated_conjugate_gradient_descent is used.

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\mathcal{M}$ of f as a function (M, p) -> X or a function (M, X, p) -> X computing X in-place
  • Hess_f: the (Riemannian) Hessian $\operatorname{Hess}f: T_{p}\mathcal{M} → T_{p}\mathcal{M}$ of f as a function (M, p, X) -> Y or a function (M, Y, p, X) -> Y computing Y in-place
  • p::P: a point on the manifold $\mathcal{M}$

the cost f and its gradient and Hessian might also be provided as a ManifoldHessianObjective mho

Keyword arguments

  • acceptance_rate=0.1: accept/reject threshold: if ρ (the performance ratio for the iterate) is larger than the acceptance rate ρ', the candidate is accepted. This value should be between $0$ and $\frac{1}{4}$
  • augmentation_threshold=0.75: trust-region augmentation threshold: if ρ is larger than this threshold and the subsolver solution reached the trust region boundary (for instance due to negative curvature), the radius is extended (augmented)
  • augmentation_factor=2.0: trust-region augmentation factor
  • callbacks::D = Dict{Symbol,Function}(): provided callback functions given either as a single function (symbol, problem, state, k) called in every hook or as a (vector of) pairs :hook => function, which are processed by process_callbacks_arg. As key you can either pass single symbol or an array of symbols to indicate a callback should be added in multiple places
  • evaluation::AbstractEvaluationType=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating their 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.
  • κ=0.1: the linear convergence target rate of the tCG method truncated_conjugate_gradient_descent, and is used in a stopping criterion therein
  • max_trust_region_radius=sqrt(manifold_dimension(M)): the maximum trust-region radius
  • preconditioner: a preconditioner for the Hessian H. This is either an allocating function (M, p, X) -> Y or an in-place function (M, Y, p, X) -> Y, see evaluation, and by default set to the identity.
  • project!=copyto!: for numerical stability it is possible to project onto the tangent space after every iteration. the function has to work inplace of Y, that is (M, Y, p, X) -> Y, where X and Y can be the same memory.
  • randomize=false: indicate whether the initial tangent vector for the subsolver is chosen at random or not. This disables preconditioning.
  • ρ_regularization=1e3: regularize the performance evaluation $ρ$ to avoid numerical inaccuracies.
  • reduction_factor=0.25: trust-region reduction factor
  • reduction_threshold=0.1: trust-region reduction threshold: if ρ is below this threshold, the trust region radius is reduced by reduction_factor.
  • retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
  • σ=randomize ? 1e-3 : 0.0: Gaussian standard deviation when creating the random initial tangent vector; a value of 0 disables the randomized (Cauchy point) mode
  • stopping_criterion::StoppingCriterion=StopAfterIteration(1000)|StopWhenGradientNormLess(1e-6): a functor indicating that the stopping criterion is fulfilled
  • sub_kwargs = (;): a named tuple of keyword arguments that are passed to decorate_objective! of the sub solver's objective, the decorate_state! of the sub solver's state, and the sub state constructor itself.
  • sub_stopping_criterion::StoppingCriterion=( see truncated_conjugate_gradient_descent): a functor indicating that the stopping criterion is fulfilled
  • sub_objective: the sub objective to solve, by default the TrustRegionModelObjective of mho after the objective_type conversion, possibly decorated with sub_kwargs Note that this keyword has no effect if you set the sub_problem directly.
  • sub_problem::Union{AbstractManoptProblem, F} =DefaultManoptProblem(TangentSpace(M,p), sub_objective): specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
  • sub_state::Union{AbstractManoptSolverState,AbstractEvaluationType} =TruncatedConjugateGradientState: a state to specify the sub solver to use. For a closed form solution, this indicates the type of function. See also truncated_conjugate_gradient_descent for more details.
  • θ=1.0: the superlinear convergence target rate of $1+θ$ of the tCG-method truncated_conjugate_gradient_descent, and is used in a stopping criterion therein
  • trust_region_radius=max_trust_region_radius / 8: the initial trust-region radius

All other keyword arguments are passed to decorate_state! for state decorators or decorate_objective! for objective decorators, respectively.

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.

See also

truncated_conjugate_gradient_descent

source

State

Manopt.TrustRegionsState — Type
TrustRegionsState <: AbstractSubProblemSolverState

Store the state of the trust-regions solver.

Fields

  • acceptance_rate: a lower bound of the performance ratio for the iterate that decides if the iteration is accepted or not.
  • augmentation_factor: the factor to enlarge the trust-region radius by
  • augmentation_threshold: an upper bound of the performance ratio; if it is exceeded and the sub solver reached the trust-region boundary, the radius is enlarged
  • callbacks::D: provided callback functions given as a dictionary with symbols as keys
  • HX, HY: interim storage (to avoid allocation) of $\operatorname{Hess} f(p)[⋅]$ for X and Y
  • max_trust_region_radius: the maximum trust-region radius
  • p::P: a point on the manifold $\mathcal{M}$ storing the current iterate
  • p_proposal: the tentative next iterate, that is p retracted by Y
  • project!: for numerical stability it is possible to project onto the tangent space after every iteration. the function has to work inplace of Y, that is (M, Y, p, X) -> Y, where X and Y can be the same memory.
  • reduction_factor: the factor to shrink the trust-region radius by
  • reduction_threshold: a lower bound of the performance ratio below which the trust-region radius is shrunk
  • retraction_method::AbstractRetractionMethod: a retraction $\operatorname{retr}$ to use, see the section on retractions
  • stop::StoppingCriterion: a functor indicating that the stopping criterion is fulfilled
  • randomize: indicate whether the initial tangent vector for the subsolver (Y) is chosen at random or not
  • ρ_regularization: regularize the model fitness $ρ$ to avoid division by zero
  • sub_problem::Union{AbstractManoptProblem, F}: specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
  • sub_state::Union{AbstractManoptSolverState,AbstractEvaluationType}: a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.
  • σ: Gaussian standard deviation when creating the random initial tangent vector Defaults to 0 unless randomize is set; a value of 0 disables the randomized (Cauchy point) mode.
  • τ: the scaling factor of the Cauchy point step (only used in the randomized mode)
  • trust_region_radius: the trust-region radius
  • X::T: a tangent vector at the point $p$ on the manifold $\mathcal{M}$
  • Y: the solution (tangent vector) of the subsolver

Constructors

TrustRegionsState(M, mho::AbstractManifoldHessianObjective; kwargs...)TrustRegionsState(M, sub_problem, sub_state; kwargs...)TrustRegionsState(M, sub_problem; evaluation=AllocatingEvaluation(), kwargs...)

create a trust region state.

  • given a AbstractManifoldHessianObjective mho, the default sub solver, a TruncatedConjugateGradientState with mho used to define the problem on a tangent space is created
  • given a sub_problem and an evaluation= keyword, the sub problem solver is assumed to be the closed form solution, where evaluation determines how to call the sub function. It is expected to be of the form (M, Y, p, Δ) -> Y for the in-place and (M, p, Δ) -> Y for the allocating evaluation, that is it minimizes the model within the trust region of radius Δ around p.

Input

Keyword arguments

  • acceptance_rate=0.1
  • augmentation_factor=2.0
  • augmentation_threshold=0.75
  • callbacks::D = Dict{Symbol,Function}(): provided callback functions given as a dictionary with symbols as keys
  • max_trust_region_radius=sqrt(manifold_dimension(M))
  • p::P =rand(M): a point on the manifold $\mathcal{M}$ to specify the initial value
  • project!=copyto!
  • reduction_factor=0.25
  • reduction_threshold=0.1
  • retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
  • stopping_criterion::StoppingCriterion=StopAfterIteration(1000)|StopWhenGradientNormLess(1e-6): a functor indicating that the stopping criterion is fulfilled
  • randomize=false
  • ρ_regularization=1000.0
  • σ=randomize ? 1e-3 : 0.0: Gaussian standard deviation when creating the random initial tangent vector; a value of 0 disables the randomized (Cauchy point) mode
  • trust_region_radius=max_trust_region_radius / 8
  • X::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$ to specify the representation of a tangent vector

See also

trust_regions

source

Technical details

The trust_regions solver requires the following functions of a manifold to be available

  • A retract!(M, q, p, X); it is recommended to set the default_retraction_method to a favorite retraction. If this default is set, a retraction_method= does not have to be specified.
  • inner(M, p, X, Y) is used within the algorithm step. By default the stopping criterion uses the norm as well, to stop when the norm of the gradient is small, but if you implemented inner, the norm is provided already.
  • if you do not provide both a max_trust_region_radius= and a sub_stopping_criterion=, a manifold_dimension is required, since the defaults of both are computed from it.
  • A copyto!(M, q, p) and copy(M,p) for points.
  • By default the tangent vectors are initialized calling zero_vector(M,p).

Literature

[ABG06]
P.-A. Absil, C. Baker and K. Gallivan. Trust-Region Methods on Riemannian Manifolds. Foundations of Computational Mathematics 7, 303–330 (2006).
[CGT00]
A. R. Conn, N. I. Gould and P. L. Toint. Trust Region Methods (Society for Industrial and Applied Mathematics, 2000).