Adaptive regularization with cubics

adaptive_regularization_with_cubics(M, f, grad_f, Hess_f, p=rand(M); kwargs...)
adaptive_regularization_with_cubics(M, f, grad_f, p=rand(M); kwargs...)
adaptive_regularization_with_cubics(M, mho, p=rand(M); kwargs...)
adaptive_regularization_with_cubics!(M, f, grad_f, Hess_f, p; kwargs...)
adaptive_regularization_with_cubics!(M, f, grad_f, p; kwargs...)
adaptive_regularization_with_cubics!(M, mho, p; kwargs...)

Solve an optimization problem on the manifold M by iteratively minimizing

\[m_k(X) = f(p_k) + ⟨X,\operatorname{grad} f(p_k)⟩_{p_k} + \frac{1}{2} ⟨X,\operatorname{Hess} f(p_k)[X]⟩_{p_k} + \frac{σ_k}{3}\lVert X \rVert^3\]

on the tangent space at the current iterate $p_k$, where $X ∈ T_{p_k}\mathcal{M}$ and $σ_k > 0$ is a regularization parameter.

Let $X_k$ denote the minimizer of the model $m_k$ and use the model improvement

\[ ρ_k = \frac{f(p_k) - f(\operatorname{retr}_{p_k}(X_k))}{m_k(0) - m_k(X_k) + \frac{σ_k}{3}\lVert X_k \rVert^3}\]

With two thresholds $η_2 ≥ η_1 > 0$ set $p_{k+1} = \operatorname{retr}_{p_k}(X_k)$ if $ρ ≥ η_1$ and reject the candidate otherwise, that is, set $p_{k+1} = p_k$.

Further, the update of the regularization parameter using the factors $0 < γ_1 < 1 < γ_2$ reads

\[σ_{k+1} = \begin{cases} \max\{σ_{\min}, γ_1σ_k\} & \text{ if } ρ \geq η_2 &\text{ (the model was very successful)},\\ σ_k & \text{ if } ρ ∈ [η_1, η_2)&\text{ (the model was successful)},\\ γ_2σ_k & \text{ if } ρ < η_1&\text{ (the model was unsuccessful)}. \end{cases}\]

For more details see [ABBC20].

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

Keyword arguments

• σ=100.0 / sqrt(manifold_dimension(M)): initial regularization parameter
• σmin=1e-10: minimal regularization value $σ_{\min}$
• η1=0.1: lower model success threshold
• η2=0.9: upper model success threshold
• γ1=0.1: regularization reduction factor (for the success case)
• γ2=2.0: regularization increment factor (for the non-success case)
• 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.
• 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
• initial_tangent_vector=zero_vector(M, p): initialize any tangent vector data,
• maxIterLanczos=min(300, manifold_dimension(M)): a shortcut to set the stopping criterion in the sub solver,
• ρ_regularization=1e3: a regularization to avoid dividing by zero for small values of cost and model
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stopping_criterion::StoppingCriterion=StopAfterIteration(40)|StopWhenGradientNormLess(1e-9)|StopWhenAllLanczosVectorsUsed(maxIterLanczos-1): a functor indicating that the stopping criterion is fulfilled the last criterion is only part of the default if the sub_state is a LanczosState
• sub_stopping_criterion=StopAfterIteration(maxIterLanczos)|StopWhenFirstOrderProgress(θ): the stopping criterion of the default sub solver
• 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.
• θ=0.5: the $θ$ parameter of the StopWhenFirstOrderProgress within the default sub_stopping_criterion=
• sub_objective=nothing: a shortcut to modify the objective of the subproblem used within in the sub_problem= keyword By default, this is initialized as an AdaptiveRegularizationWithCubicsModelObjective, which can further be decorated by using the sub_kwargs= keyword.
• sub_state::Union{AbstractManoptSolverState,AbstractEvaluationType} =LanczosState(TangentSpace(M, copy(M, p))): a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.
• sub_problem::Union{AbstractManoptProblem, F} =DefaultManoptProblem(TangentSpace(M, copy(M, p)), sub_objective): specify a problem for a solver or a closed form solution function, which can be allocating or in-place.

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

If you provide the ManifoldHessianObjective directly, the evaluation= keyword is ignored. The decorations are still applied to the objective.

If you activate tutorial mode (cf. is_tutorial_mode), this solver provides additional debug warnings.

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.

adaptive_regularization_with_cubics(M, f, grad_f, Hess_f, p=rand(M); kwargs...)
adaptive_regularization_with_cubics(M, f, grad_f, p=rand(M); kwargs...)
adaptive_regularization_with_cubics(M, mho, p=rand(M); kwargs...)
adaptive_regularization_with_cubics!(M, f, grad_f, Hess_f, p; kwargs...)
adaptive_regularization_with_cubics!(M, f, grad_f, p; kwargs...)
adaptive_regularization_with_cubics!(M, mho, p; kwargs...)

Solve an optimization problem on the manifold M by iteratively minimizing

\[m_k(X) = f(p_k) + ⟨X,\operatorname{grad} f(p_k)⟩_{p_k} + \frac{1}{2} ⟨X,\operatorname{Hess} f(p_k)[X]⟩_{p_k} + \frac{σ_k}{3}\lVert X \rVert^3\]

on the tangent space at the current iterate $p_k$, where $X ∈ T_{p_k}\mathcal{M}$ and $σ_k > 0$ is a regularization parameter.

Let $X_k$ denote the minimizer of the model $m_k$ and use the model improvement

\[ ρ_k = \frac{f(p_k) - f(\operatorname{retr}_{p_k}(X_k))}{m_k(0) - m_k(X_k) + \frac{σ_k}{3}\lVert X_k \rVert^3}\]

With two thresholds $η_2 ≥ η_1 > 0$ set $p_{k+1} = \operatorname{retr}_{p_k}(X_k)$ if $ρ ≥ η_1$ and reject the candidate otherwise, that is, set $p_{k+1} = p_k$.

Further, the update of the regularization parameter using the factors $0 < γ_1 < 1 < γ_2$ reads

\[σ_{k+1} = \begin{cases} \max\{σ_{\min}, γ_1σ_k\} & \text{ if } ρ \geq η_2 &\text{ (the model was very successful)},\\ σ_k & \text{ if } ρ ∈ [η_1, η_2)&\text{ (the model was successful)},\\ γ_2σ_k & \text{ if } ρ < η_1&\text{ (the model was unsuccessful)}. \end{cases}\]

For more details see [ABBC20].

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

Keyword arguments

• σ=100.0 / sqrt(manifold_dimension(M)): initial regularization parameter
• σmin=1e-10: minimal regularization value $σ_{\min}$
• η1=0.1: lower model success threshold
• η2=0.9: upper model success threshold
• γ1=0.1: regularization reduction factor (for the success case)
• γ2=2.0: regularization increment factor (for the non-success case)
• 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.
• 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
• initial_tangent_vector=zero_vector(M, p): initialize any tangent vector data,
• maxIterLanczos=min(300, manifold_dimension(M)): a shortcut to set the stopping criterion in the sub solver,
• ρ_regularization=1e3: a regularization to avoid dividing by zero for small values of cost and model
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stopping_criterion::StoppingCriterion=StopAfterIteration(40)|StopWhenGradientNormLess(1e-9)|StopWhenAllLanczosVectorsUsed(maxIterLanczos-1): a functor indicating that the stopping criterion is fulfilled the last criterion is only part of the default if the sub_state is a LanczosState
• sub_stopping_criterion=StopAfterIteration(maxIterLanczos)|StopWhenFirstOrderProgress(θ): the stopping criterion of the default sub solver
• 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.
• θ=0.5: the $θ$ parameter of the StopWhenFirstOrderProgress within the default sub_stopping_criterion=
• sub_objective=nothing: a shortcut to modify the objective of the subproblem used within in the sub_problem= keyword By default, this is initialized as an AdaptiveRegularizationWithCubicsModelObjective, which can further be decorated by using the sub_kwargs= keyword.
• sub_state::Union{AbstractManoptSolverState,AbstractEvaluationType} =LanczosState(TangentSpace(M, copy(M, p))): a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.
• sub_problem::Union{AbstractManoptProblem, F} =DefaultManoptProblem(TangentSpace(M, copy(M, p)), sub_objective): specify a problem for a solver or a closed form solution function, which can be allocating or in-place.

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

If you provide the ManifoldHessianObjective directly, the evaluation= keyword is ignored. The decorations are still applied to the objective.

If you activate tutorial mode (cf. is_tutorial_mode), this solver provides additional debug warnings.

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.

AdaptiveRegularizationState{P,T} <: AbstractManoptSolverState

A state for the adaptive_regularization_with_cubics solver.

Fields

• η1, η2: bounds for evaluating the regularization parameter
• γ1, γ2: shrinking and expansion factors for regularization parameter σ
• H: the current Hessian evaluation
• p::P: a point on the manifold $\mathcal{M}$ storing the current iterate
• q: a point for the candidates to evaluate model and ρ
• X::T: a tangent vector at the point $p$ on the manifold $\mathcal{M}$ storing the gradient at the current iterate
• s: the tangent vector step resulting from minimizing the model problem in the tangent space $T_{p}\mathcal{M}$
• σ: the current cubic regularization parameter
• σmin: lower bound for the cubic regularization parameter
• ρ_regularization: regularization parameter for computing ρ. When approaching convergence ρ may be difficult to compute with numerator and denominator approaching zero. Regularizing the ratio lets ρ go to 1 near convergence.
• ρ: the current regularized ratio of actual improvement and model improvement.
• ρ_denominator: a value to store the denominator from the computation of ρ to allow for a warning or error when this value is non-positive.
• 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
• 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.
• callbacks::D: provided callback functions given as a dictionary with symbols as keys

Constructors

AdaptiveRegularizationState(M, sub_problem, sub_state; kwargs...)AdaptiveRegularizationState(M, sub_problem; evaluation=AllocatingEvaluation(), kwargs...)

Construct the solver state with all fields stated as keyword arguments and the following defaults. 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.

Keyword arguments

• η1=0.1
• η2=0.9
• γ1=0.1
• γ2=2.0
• σ=100.0/sqrt(manifold_dimension(M))
• σmin=1e-10
• ρ_regularization=1e3
• 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.
• p::P =rand(M): a point on the manifold $\mathcal{M}$
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• callbacks::D = Dict{Symbol,Function}(): provided callback functions given as a dictionary with symbols as keys
• stopping_criterion::StoppingCriterion=StopAfterIteration(100): a functor indicating that the stopping criterion is fulfilled
• X::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$

LanczosState{T,R,SC,SCN,B,TM,C,CA} <: AbstractManoptSolverState

Solve the adaptive regularized subproblem with a Lanczos iteration

Fields

• stop::StoppingCriterion: a functor indicating that the stopping criterion is fulfilled
• stop_newton::StoppingCriterion: a functor indicating that the stopping criterion is fulfilled used for the inner Newton iteration
• callbacks::D: provided callback functions given as a dictionary with symbols as keys
• σ: the current regularization parameter
• X: the iterate
• Lanczos_vectors: the obtained Lanczos vectors
• tridig_matrix: the tridiagonal coefficient matrix T
• coefficients: the coefficients $y_1,…,y_k$ that determine the solution
• Hp: a temporary tangent vector containing the evaluation of the Hessian
• Hp_residual: a temporary tangent vector containing the residual to the Hessian
• S: the current obtained / approximated solution

Constructor

LanczosState(TpM::TangentSpace; kwargs...)

Keyword arguments

• X::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$ storing the current iterate
• callbacks::D = Dict{Symbol,Function}(): provided callback functions given as a dictionary with symbols as keys
• maxIterLanczos=200: shortcut to set the maximal number of iterations in the stopping_criterion=
• θ=0.5: set the parameter in the StopWhenFirstOrderProgress within the default stopping_criterion=.
• stopping_criterion::StoppingCriterion=StopAfterIteration(maxIterLanczos)|StopWhenFirstOrderProgress(θ): a functor indicating that the stopping criterion is fulfilled
• stopping_criterion_newton::StoppingCriterion=StopAfterIteration(200): a functor indicating that the stopping criterion is fulfilled used for the inner Newton iteration
• σ=10.0: specify the regularization parameter

AdaptiveRegularizationWithCubicsModelObjective <: AbstractManifoldSubObjective

A model for the adaptive regularization with Cubics

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

cf. Eq. (33) in [ABBC20]

Fields

• objective: an AbstractManifoldHessianObjective providing $f$, its gradient and Hessian
• σ: the current (cubic) regularization parameter

Constructors

AdaptiveRegularizationWithCubicsModelObjective(mho, σ=1.0)

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

get_cost(TpM, arcmo::AdaptiveRegularizationWithCubicsModelObjective, X)

Evaluate the tangent space AdaptiveRegularizationWithCubicsModelObjective

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

at X, cf. Eq. (33) in [ABBC20].

get_gradient(TpM, arcmo::AdaptiveRegularizationWithCubicsModelObjective, X)

Evaluate the gradient of the AdaptiveRegularizationWithCubicsModelObjective

\[\operatorname{grad} m(X) = \operatorname{grad} f(p) + \operatorname{Hess} f(p)[X] + σ\lVert X \rVert X,\]

at X, cf. Eq. (37) in [ABBC20].

StopWhenAllLanczosVectorsUsed <: StoppingCriterion

When an inner iteration has used up all Lanczos vectors, then this stopping criterion is a fallback / security stopping criterion to not access a non-existing field in the array allocated for vectors.

Note that this stopping criterion (for now) is only implemented for the case that an AdaptiveRegularizationState uses a LanczosState subsolver.

Fields

• maxLanczosVectors: maximal number of Lanczos vectors
• at_iteration indicates at which iteration (including k=0) the stopping criterion was fulfilled and is -1 while it is not fulfilled.

Constructor

StopWhenAllLanczosVectorsUsed(maxLanczosVectors::Int)

StopWhenFirstOrderProgress <: StoppingCriterion

A stopping criterion related to the Riemannian adaptive regularization with cubics (ARC) solver indicating that the model function at the current (outer) iterate,

\[m_k(X) = f(p_k) + ⟨X,\operatorname{grad} f(p_k)⟩_{p_k} + \frac{1}{2} ⟨X,\operatorname{Hess} f(p_k)[X]⟩_{p_k} + \frac{σ_k}{3}\lVert X \rVert^3\]

defined on the tangent space $T_{p}\mathcal{M}$ fulfills at the current iterate $X_k$ that

\[\lVert \operatorname{grad} m(X_k) \rVert ≤ θ \lVert X_k \rVert^2\]

Fields

• θ: the factor $θ$ in the second condition
• at_iteration::Int: an integer indicating at which iteration the stopping criterion last indicated to stop, which might also be before the solver started (0). Any negative value indicates that this was not yet the case.

Constructor

StopWhenFirstOrderProgress(θ)