Convex bundle method

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

perform a convex bundle method $p^{(k+1)} = \operatorname{retr}_{p^{(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, $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=eps(): : tolerance parameter for the linearization errors.
• atol_λ=eps() : tolerance parameter for the convex coefficients in $λ$.
• bundle_cap=25`
• callbacks::D = Dict{Symbol,Function}(): provided callback functions . A single function (symbol, problem, state, k) called in every hook, a (vector of) pairs :hook => function or will be 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
• diameter=50.0: 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 to 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 its 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.
• m=1e-3: : the parameter to test the decrease of the cost: $f(q_{k+1}) ≤ f(p_k) + m ξ$.
• stepsize::Stepsize=default_stepsize(M,ConvexBundleMethodState): 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} =AllocatingEvaluation´ `: specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
• sub_state::Union{AbstractManoptProblem, F} =convex_bundle_method_subsolver`: 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}$

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 $p^{(k+1)} = \operatorname{retr}_{p^{(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, $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=eps(): : tolerance parameter for the linearization errors.
• atol_λ=eps() : tolerance parameter for the convex coefficients in $λ$.
• bundle_cap=25`
• callbacks::D = Dict{Symbol,Function}(): provided callback functions . A single function (symbol, problem, state, k) called in every hook, a (vector of) pairs :hook => function or will be 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
• diameter=50.0: 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 to 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 its 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.
• m=1e-3: : the parameter to test the decrease of the cost: $f(q_{k+1}) ≤ f(p_k) + m ξ$.
• stepsize::Stepsize=default_stepsize(M,ConvexBundleMethodState): 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} =AllocatingEvaluation´ `: specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
• sub_state::Union{AbstractManoptProblem, F} =convex_bundle_method_subsolver`: 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}$

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 offas a function(M,p) -> bthat evaluates to true when the current candidate is in the domain off`, 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
• 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 ξ$.
• 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 slution of the subproblem
• ξ: 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{AbstractManoptProblem, F}: 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{AbstractManoptProblem, F}: 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) -> isfinite(f(M, p))
• 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
• k_min=0
• m=1e-2
• p::P =rand(M): a point on the manifold $\mathcal{M}$ to specify the initial value
• 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): 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.

λ = 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} \Bigl\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 we are $q =\operatorname{retr}_p(X)$ yields a point closer to $p$ than $\lVert X \rVert_{p}$ or $q$ is not on 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: how to update $s$ in the decrease step
• initial_stepsize`: specify an initial step size
• 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. For the domain 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{-ω}δ\cot(\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.