Convex Bundle Method

convex_bundle_method(M, f, ∂f, p)

perform a convex bundle method $p_{j+1} = \mathrm{retr}(p_k, -g_k)$, where $\mathrm{retr}$ is a retraction and

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

$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: a manifold $\mathcal M$
• f: a cost function $f:\mathcal M→ℝ$ to minimize
• ∂f: the subgradient $∂f: \mathcal M → T\mathcal M$ of f restricted to always only returning one value/element from the subdifferential. This function can be passed as an allocation function (M, p) -> X or a mutating function (M, X, p) -> X, see evaluation.
• p: (rand(M)) an initial value $p_0 ∈ \mathcal M$

Optional

• atol_λ: (eps()) tolerance parameter for the convex coefficients in λ.
• atol_errors: (eps()) tolerance parameter for the linearization errors.
• m: (1e-3) the parameter to test the decrease of the cost: $f(q_{k+1}) \le f(p_k) + m \xi$.
• 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, e.g. : domain = (M, p) -> p ∈ dom f(M, p) ? true : false.
• k_max: upper bound on the sectional curvature of the manifold.
• k_size: (100) sample size for the estimation of the bounds on the sectional curvature of the manifold ifk_max` is not provided.
• p_estimate: (p) the point around which to estimate the sectional curvature of the manifold.
• α: ((i) -> one(number_eltype(X)) / i) a function for evaluating suitable stepsizes when obtaining candidate points at iteration i.
• ϱ: curvature-dependent bound.
• evaluation: (AllocatingEvaluation) specify whether the subgradient works by allocation (default) form ∂f(M, q) or InplaceEvaluation in place, i.e. is of the form ∂f!(M, X, p).
• inverse_retraction_method: (default_inverse_retraction_method(M, typeof(p))) an inverse retraction method to use
• retraction_method: (default_retraction_method(M, typeof(p))) a retraction(M, p, X) to use.
• stopping_criterion: (StopWhenLagrangeMultiplierLess(1e-8)) a functor, seeStoppingCriterion, indicating when to stop
• vector_transport_method: (default_vector_transport_method(M, typeof(p))) a vector transport method to use
• sub_problem: a function evaluating with new allocations that solves the sub problem on M given the last serious iterate p_last_serious, the linearization errors linearization_errors, and the transported subgradients transported_subgradients

Output

the obtained (approximate) minimizer $p^*$, see get_solver_return for details

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

perform a bundle method $p_{j+1} = \mathrm{retr}(p_k, -g_k)$ in place of p.

Input

• M: a manifold $\mathcal M$
• f: a cost function $f:\mathcal M→ℝ$ to minimize
• ∂f: the (sub)gradient $∂f:\mathcal M→ T\mathcal M$ of F restricted to always only returning one value/element from the subdifferential. This function can be passed as an allocation function (M, p) -> X or a mutating function (M, X, p) -> X, see evaluation.
• p: an initial value $p_0=p ∈ \mathcal M$

for more details and all optional parameters, see convex_bundle_method.

ConvexBundleMethodState <: AbstractManoptSolverState

Stores option values for a convex_bundle_method solver.

Fields

• atol_λ: (eps()) tolerance parameter for the convex coefficients in λ
• atol_errors: (eps()) tolerance parameter for the linearization errors
• bundle: bundle that collects each iterate with the computed subgradient at the iterate
• bundle_cap: (25) the maximal number of elements the bundle is allowed to remember
• 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, e.g. : domain = (M, p) -> p ∈ dom f(M, p) ? true : false
• g: descent direction
• inverse_retraction_method: the inverse retraction to use within
• linearization_errors: linearization errors at the last serious step
• m: (1e-3) the parameter to test the decrease of the cost: $f(q_{k+1}) \le f(p_k) + m \xi$.
• p: current candidate point
• p_last_serious: last serious iterate
• retraction_method: the retraction to use within
• stop: a StoppingCriterion
• transported_subgradients: subgradients of the bundle that are transported to plastserious
• vector_transport_method: the vector transport method to use within
• X: (zero_vector(M, p)) the current element from the possible subgradients at p that was last evaluated.
• stepsize: (ConstantStepsize(M)) a Stepsize
• ε: convex combination of the linearization errors
• λ: convex coefficients that solve the subproblem
• ξ: the stopping parameter given by $ξ = -\lvert g\rvert^2 – ε$
• ϱ: curvature-dependent bound
• sub_problem: ([convex_bundle_method_subsolver]) a function that solves the sub problem on M given the last serious iterate p_last_serious, the linearization errors linearization_errors, and the transported subgradients transported_subgradients,
• sub_state: an AbstractEvaluationType indicating whether sub_problem works inplace of λ or allocates a solution

Constructor

ConvexBundleMethodState(M::AbstractManifold, p; kwargs...)

with keywords for all fields with defaults besides p_last_serious which obtains the same type as p. You can use e.g. X= to specify the type of tangent vector to use

Keyword arguments

• k_max: upper bound on the sectional curvature of the manifold
• k_size: (100) sample size for the estimation of the bounds on the sectional curvature of the manifold
• p_estimate: (p) the point around which to estimate the sectional curvature of the manifold

StopWhenLagrangeMultiplierLess <: StoppingCriterion

Stopping Criteria for Lagrange multipliers.

Currenlty these are meant for the convex_bundle_method and proximal_bundle_method, where based on the Lagrange multipliers an approximate (sub)gradient $g$ and an error estimate $ε$ is computed.

In mode=:both we require that both $ε$ and $\lvert g \rvert$ are smaller than their tolerances for the convex_bundle_method, and that $c$ and $\lvert d \rvert$ are smaller than their tolerances for the proximal_bundle_method.

In the mode=:estimate we require that, for the convex_bundle_method $-ξ = \lvert g \rvert^2 + ε$ is less than a given tolerance. For the proximal_bundle_method, the equation reads $-ν = μ \lvert d \rvert^2 + c$.

Constructors

StopWhenLagrangeMultiplierLess(tolerance=1e-6; mode::Symbol=:estimate)

Create the stopping criterion for one of the modes mentioned. Note that tolerance can be a single number for the :estimate case, but a vector of two values is required for the :both mode. Here the first entry specifies the tolerance for $ε$ ($c$), the second the tolerance for $\lvert g \rvert$ ($\lvert d \rvert$), respectively.

DebugWarnIfLagrangeMultiplierIncreases <: DebugAction

print a warning if the Lagrange parameter based value $-ξ$ of the bundle method increases.

Constructor

DebugWarnIfLagrangeMultiplierIncreases(warn=:Once; tol=1e2)

Initialize the warning to warning level (:Once) and introduce a tolerance for the test of 1e2.

The warn level can be set to :Once to only warn the first time the cost increases, to :Always to report an increase every time it happens, and it can be set to :No to deactivate the warning, then this DebugAction is inactive. All other symbols are handled as if they were :Always:

λ = 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} λ_j \, c_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\} \cup \{k\}$. See [BHJ24] for mre details

estimate_sectional_curvature(M::AbstractManifold, p)

Estimate the sectional curvature of a manifold $\mathcal M$ at a point $p \in \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

\[\zeta_{1, ω}(δ) \coloneqq \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

\[\zeta_{2, Ω}(δ) \coloneqq \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.