Convex bundle method

convex_bundle_method(M, f, ∂f, p)
convex_bundle_method!(M, f, ∂f, p)

perform a convex bundle method with the candidate update $q_{k+1} = \operatorname{retr}_{p_k}(-t_k g_k)$ where

\[g_k = \sum_{j ∈ J_k} λ_j^k \mathrm{P}_{p_k←q_j}X_{q_j},\]

and $p_k$ is the last serious iterate, $t_k$ the step size of iteration $k$, $X_{q_j} ∈ ∂f(q_j)$, and the $λ_j^k$ are solutions to the quadratic subproblem provided by the convex_bundle_method_subsolver.

Though the subdifferential might be set valued, the argument ∂f should always return one element from the subdifferential, but not necessarily deterministic.

For more details, see [BHJ24].

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
• f: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v
• ∂f: the subgradient $∂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. This function should always only return one element from the subgradient.
• p::P: a point on the manifold $\mathcal{M}$

Keyword arguments

• atol_errors=sqrt(eps()): tolerance parameter for the linearization errors.
• atol_λ=sqrt(eps()): tolerance parameter for the convex coefficients in $λ$.
• bundle_cap=25
• 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
• contraction_factor=0.975: the contraction factor passed to the default DomainBackTracking step size.
• debug=[DebugWarnIfLagrangeMultiplierIncreases()]: by default warn when the stopping parameter increases; pass debug=[] to deactivate.
• diameter=π/3: estimate for the diameter of the level set of the objective function at the starting point.
• domain=(M, p) -> isfinite(f(M, p)): a function that evaluates to true when the current candidate is in the domain of the objective f, and false otherwise.
• 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.
• inverse_retraction_method::AbstractInverseRetractionMethod=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• k_max=0: upper bound on the sectional curvature of the manifold.
• k_min=0: lower bound on the sectional curvature of the manifold.
• m=1e-3: the parameter to test the decrease of the cost: $f(q_{k+1}) ≤ f(p_k) + m t_k ξ$, where $t_k$ is the step size of iteration $k$.
• p_estimate=p: the center point for the curvature estimation.
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize::Stepsize=DomainBackTracking(; contraction_factor=0.975): a functor inheriting from Stepsize to determine a step size
• stopping_criterion::StoppingCriterion=StopWhenLagrangeMultiplierLess(1e-8)|StopAfterIteration(5000): a functor indicating that the stopping criterion is fulfilled
• sub_problem::Union{AbstractManoptProblem, F} =convex_bundle_method_subsolver: specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
• sub_state::Union{AbstractManoptSolverState,AbstractEvaluationType} =AllocatingEvaluation(): a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• X::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$ to specify the type of tangent vector to use.
• ϱ=nothing: curvature-dependent convexification coefficient; computed from k_min, k_max, and diameter if nothing.

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.

convex_bundle_method(M, f, ∂f, p)
convex_bundle_method!(M, f, ∂f, p)

perform a convex bundle method with the candidate update $q_{k+1} = \operatorname{retr}_{p_k}(-t_k g_k)$ where

\[g_k = \sum_{j ∈ J_k} λ_j^k \mathrm{P}_{p_k←q_j}X_{q_j},\]

and $p_k$ is the last serious iterate, $t_k$ the step size of iteration $k$, $X_{q_j} ∈ ∂f(q_j)$, and the $λ_j^k$ are solutions to the quadratic subproblem provided by the convex_bundle_method_subsolver.

Though the subdifferential might be set valued, the argument ∂f should always return one element from the subdifferential, but not necessarily deterministic.

For more details, see [BHJ24].

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
• f: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v
• ∂f: the subgradient $∂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. This function should always only return one element from the subgradient.
• p::P: a point on the manifold $\mathcal{M}$

Keyword arguments

• atol_errors=sqrt(eps()): tolerance parameter for the linearization errors.
• atol_λ=sqrt(eps()): tolerance parameter for the convex coefficients in $λ$.
• bundle_cap=25
• 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
• contraction_factor=0.975: the contraction factor passed to the default DomainBackTracking step size.
• debug=[DebugWarnIfLagrangeMultiplierIncreases()]: by default warn when the stopping parameter increases; pass debug=[] to deactivate.
• diameter=π/3: estimate for the diameter of the level set of the objective function at the starting point.
• domain=(M, p) -> isfinite(f(M, p)): a function that evaluates to true when the current candidate is in the domain of the objective f, and false otherwise.
• 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.
• inverse_retraction_method::AbstractInverseRetractionMethod=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• k_max=0: upper bound on the sectional curvature of the manifold.
• k_min=0: lower bound on the sectional curvature of the manifold.
• m=1e-3: the parameter to test the decrease of the cost: $f(q_{k+1}) ≤ f(p_k) + m t_k ξ$, where $t_k$ is the step size of iteration $k$.
• p_estimate=p: the center point for the curvature estimation.
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize::Stepsize=DomainBackTracking(; contraction_factor=0.975): a functor inheriting from Stepsize to determine a step size
• stopping_criterion::StoppingCriterion=StopWhenLagrangeMultiplierLess(1e-8)|StopAfterIteration(5000): a functor indicating that the stopping criterion is fulfilled
• sub_problem::Union{AbstractManoptProblem, F} =convex_bundle_method_subsolver: specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
• sub_state::Union{AbstractManoptSolverState,AbstractEvaluationType} =AllocatingEvaluation(): a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• X::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$ to specify the type of tangent vector to use.
• ϱ=nothing: curvature-dependent convexification coefficient; computed from k_min, k_max, and diameter if nothing.

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.

ConvexBundleMethodState <: AbstractManoptSolverState

Stores option values for a convex_bundle_method solver.

Fields

The following fields require a (real) number type R, as well as point type P and a tangent vector type T

• callbacks::D: provided callback functions given as a dictionary with symbols as keys
• atol_λ::R: tolerance parameter for the convex coefficients in λ
• atol_errors::R: tolerance parameter for the linearization errors
• bundle<:AbstractVector{Tuple{<:P,<:T}}: bundle that collects each iterate with the computed subgradient at the iterate
• bundle_cap::Int: the maximal number of elements the bundle is allowed to remember
• diameter::R: estimate for the diameter of the level set of the objective function at the starting point
• domain: the domain of $f$ as a function (M, p) -> b that evaluates to true when the current candidate is in the domain of f, and false otherwise,
• g::T: descent direction
• inverse_retraction_method::AbstractInverseRetractionMethod: an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• k_max::R: upper bound on the sectional curvature of the manifold
• k_min::R: lower bound on the sectional curvature of the manifold
• last_stepsize::R: the last computed stepsize
• linearization_errors<:AbstractVector{<:R}: linearization errors at the last serious step
• m::R: the parameter to test the decrease of the cost: $f(q_{k+1}) ≤ f(p_k) + m t_k ξ$, where $t_k$ is the step size of iteration $k$.
• null_stepsize::R: the stepsize computed in the last null step
• p::P: a point on the manifold $\mathcal{M}$ storing the current iterate
• p_last_serious::P: last serious iterate
• 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
• transported_subgradients: subgradients of the bundle that are transported to p_last_serious
• vector_transport_method::AbstractVectorTransportMethod: a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• X::T: a tangent vector at the point $p$ on the manifold $\mathcal{M}$ storing a subgradient at the current iterate
• stepsize::Stepsize: a functor inheriting from Stepsize to determine a step size
• ε::R: convex combination of the linearization errors
• λ::AbstractVector{<:R}: convex coefficients from the solution of the subproblem
• ϱ::R: curvature-dependent convexification coefficient
• ξ: the stopping parameter given by $ξ = -\lVert g \rVert^2 - ε$
• 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.

Constructor

ConvexBundleMethodState(M::AbstractManifold, sub_problem, sub_state; kwargs...)ConvexBundleMethodState(M::AbstractManifold, sub_problem=convex_bundle_method_subsolver; evaluation=AllocatingEvaluation(), kwargs...)

Generate the state for the convex_bundle_method on the manifold M

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
• 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.

Keyword arguments

Most of the following keyword arguments set default values for the fields mentioned before.

• atol_errors=eps()
• atol_λ=eps()
• bundle_cap=25
• callbacks::D = Dict{Symbol,Function}(): provided callback functions given as a dictionary with symbols as keys
• diameter=50.0
• domain=(M, p) -> true: a function that evaluates to true when the current candidate is in the domain of the objective
• inverse_retraction_method::AbstractInverseRetractionMethod=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• k_max=nothing: upper bound on the sectional curvature; estimated from k_size sample points if nothing
• k_min=nothing: lower bound on the sectional curvature; estimated from k_size sample points if nothing
• k_size=100: the number of sample points around p_estimate for the curvature estimation
• last_stepsize=1.0
• m=1e-2
• p::P =rand(M): a point on the manifold $\mathcal{M}$ to specify the initial value
• p_estimate=p: the center point for the curvature estimation
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize::Stepsize=default_stepsize(M,ConvexBundleMethodState; contraction_factor=0.975, retraction_method=retraction_method): a functor inheriting from Stepsize to determine a step size
• stopping_criterion::StoppingCriterion=StopWhenLagrangeMultiplierLess(1e-8)|StopAfterIteration(5000): a functor indicating that the stopping criterion is fulfilled
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• X::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$ to specify the type of tangent vector to use.
• ϱ=nothing: curvature-dependent convexification coefficient; computed from k_min, k_max, and diameter if nothing

λ = convex_bundle_method_subsolver(M, p_last_serious, linearization_errors, transported_subgradients)
convex_bundle_method_subsolver!(M, λ, p_last_serious, linearization_errors, transported_subgradients)

solver for the subproblem of the convex bundle method at the last serious iterate $p_k$ given the current linearization errors $c_j^k$, and transported subgradients $\mathrm{P}_{p_k←q_j} X_{q_j}$.

The computation can also be done in-place of λ.

The subproblem for the convex bundle method is

\[\begin{align*} \operatorname*{arg\,min}_{λ ∈ ℝ^{\lvert J_k \rvert}} & \frac{1}{2} \Bigl\lVert \sum_{j ∈ J_k} λ_j \mathrm{P}_{p_k←q_j} X_{q_j} \Bigr\rVert^2 + \sum_{j ∈ J_k} λ_jc_j^k \\ \text{s. t.}\quad & \sum_{j ∈ J_k} λ_j = 1, \quad λ_j ≥ 0 \quad \text{for all } j ∈ J_k, \end{align*}\]

where $J_k = \{j ∈ J_{k-1} \ | \ λ_j > 0\} ∪ \{k\}$. See [BHJ24] for more details

λ = convex_bundle_method_subsolver(M, p_last_serious, linearization_errors, transported_subgradients)
convex_bundle_method_subsolver!(M, λ, p_last_serious, linearization_errors, transported_subgradients)

solver for the subproblem of the convex bundle method at the last serious iterate $p_k$ given the current linearization errors $c_j^k$, and transported subgradients $\mathrm{P}_{p_k←q_j} X_{q_j}$.

The computation can also be done in-place of λ.

The subproblem for the convex bundle method is

\[\begin{align*} \operatorname*{arg\,min}_{λ ∈ ℝ^{\lvert J_k \rvert}} & \frac{1}{2} \Bigl\lVert \sum_{j ∈ J_k} λ_j \mathrm{P}_{p_k←q_j} X_{q_j} \Bigr\rVert^2 + \sum_{j ∈ J_k} λ_jc_j^k \\ \text{s. t.}\quad & \sum_{j ∈ J_k} λ_j = 1, \quad λ_j ≥ 0 \quad \text{for all } j ∈ J_k, \end{align*}\]

where $J_k = \{j ∈ J_{k-1} \ | \ λ_j > 0\} ∪ \{k\}$. See [BHJ24] for more details

DomainBackTrackingStepsize <: Stepsize

Implement a backtrack as long as $q = \operatorname{retr}_p(X)$ yields a point closer to $p$ than $\lVert X \rVert_{p}$ or $q$ is not in the domain. For the domain this step size requires a ConvexBundleMethodState.

DomainBackTracking(; kwargs...)
DomainBackTracking(M::AbstractManifold; kwargs...)

Specify a step size that performs a backtracking to the interior of the domain of the objective function.

Keyword arguments

• candidate_point=allocate_result(M, rand): specify a point to be used as memory for the candidate points.
• contraction_factor=0.95: the factor the step size is multiplied with in every backtracking step
• initial_stepsize=1.0: the step size the backtracking starts from
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions

NullStepBackTrackingStepsize <: Stepsize

Implement a backtracking with a geometric condition in the case of a null step. To access the parameters of the bundle method, this step size requires a ConvexBundleMethodState.

estimate_sectional_curvature(M::AbstractManifold, p)

Estimate the sectional curvature of a manifold $\mathcal{M}$ at a point $p ∈ \mathcal{M}$ on two random tangent vectors at $p$ that are orthogonal to each other.

See also

sectional_curvature

ζ_1(ω, δ)

compute a curvature-dependent bound. The formula reads

\[ζ_{1, ω}(δ) := \begin{cases} 1 & \text{ if } ω ≥ 0,\\ \sqrt{-ω}δ\coth(\sqrt{-ω}δ) & \text{ if } ω < 0\end{cases}\]

where $ω ≤ κ_p$ for all $p ∈ \mathcal{U}$ is a lower bound to the sectional curvature in a (strongly geodesically convex) bounded subset $\mathcal{U} ⊆ \mathcal{M}$ with diameter $δ$.

ζ_2(Ω, δ)

compute a curvature-dependent bound. The formula reads

\[ζ_{2, Ω}(δ) := \begin{cases} 1 & \text{ if } Ω ≤ 0,\\ \sqrt{Ω}δ\cot(\sqrt{Ω}δ) & \text{ if } Ω > 0\end{cases}\]

where $Ω ≥ κ_p$ for all $p ∈ \mathcal{U}$ is an upper bound to the sectional curvature in a (strongly geodesically convex) bounded subset $\mathcal{U} ⊆ \mathcal{M}$ with diameter $δ$.

close_point(M, p, tol; retraction_method=default_retraction_method(M, typeof(p)))

sample a random point close to $p ∈ \mathcal{M}$ within a tolerance tol and a retraction.