Convex bundle method

Manopt.convex_bundle_method β€” Function
convex_bundle_method(M, f, βˆ‚f, p)
convex_bundle_method!(M, f, βˆ‚f, p)

perform a convex bundle method p(k+1)=retr⁑p(k)(βˆ’gk)p^{(k+1)} = \operatorname{retr}_{p^{(k)}}(-g_k) where

gk=βˆ‘j∈JkΞ»jkPpk←qjXqj,g_k = \sum_{j\in J_k} Ξ»_j^k \mathrm{P}_{p_k←q_j}X_{q_j},

and pkp_k is the last serious iterate, Xqjβˆˆβˆ‚f(qj)X_{q_j} ∈ βˆ‚f(q_j), and the Ξ»jkΞ»_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 M\mathcal M
  • f: a cost function f:Mβ†’Rf: \mathcal Mβ†’ ℝ implemented as (M, p) -> v
  • βˆ‚f: a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.
  • p: a point on the manifold M\mathcal M

Keyword arguments

  • atol_Ξ»=eps() : tolerance parameter for the convex coefficients in λλ.
  • atol_errors=eps(): : tolerance parameter for the linearization errors.
  • bundle_cap=25`
  • m=1e-3: : the parameter to test the decrease of the cost: f(qk+1)≀f(pk)+mΞΎf(q_{k+1}) ≀ f(p_k) + m ΞΎ.
  • 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=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.
  • k_max=0: upper bound on the sectional curvature of the manifold.
  • stepsize=default_stepsize(M, ConvexBundleMethodState): a functor inheriting from Stepsize to determine a step size
  • inverse_retraction_method=default_inverse_retraction_method(M, typeof(p)): an inverse retraction retrβ‘βˆ’1\operatorname{retr}^{-1} to use, see the section on retractions and their inverses* inverse_retraction_method=default_inverse_retraction_method(M, typeof(p)): an inverse retraction retrβ‘βˆ’1\operatorname{retr}^{-1} to use, see the section on retractions and their inverses
  • stopping_criterion=StopWhenLagrangeMultiplierLess(1e-8)|StopAfterIteration(5000): a functor indicating that the stopping criterion is fulfilled
  • vector_transport_method=default_vector_transport_method(M, typeof(p)): a vector transport T⋅←⋅\mathcal T_{⋅←⋅} to use, see the section on vector transports
  • sub_state=convex_bundle_method_subsolver`: a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.
  • sub_problem=AllocatingEvaluation: specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
  • X=zero_vector(M, p): a tangent vector at the point pp on the manifold M\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βˆ—p^*. To obtain the whole final state of the solver, see get_solver_return for details, especially the return_state= keyword.

source
Manopt.convex_bundle_method! β€” Function
convex_bundle_method(M, f, βˆ‚f, p)
convex_bundle_method!(M, f, βˆ‚f, p)

perform a convex bundle method p(k+1)=retr⁑p(k)(βˆ’gk)p^{(k+1)} = \operatorname{retr}_{p^{(k)}}(-g_k) where

gk=βˆ‘j∈JkΞ»jkPpk←qjXqj,g_k = \sum_{j\in J_k} Ξ»_j^k \mathrm{P}_{p_k←q_j}X_{q_j},

and pkp_k is the last serious iterate, Xqjβˆˆβˆ‚f(qj)X_{q_j} ∈ βˆ‚f(q_j), and the Ξ»jkΞ»_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 M\mathcal M
  • f: a cost function f:Mβ†’Rf: \mathcal Mβ†’ ℝ implemented as (M, p) -> v
  • βˆ‚f: a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.
  • p: a point on the manifold M\mathcal M

Keyword arguments

  • atol_Ξ»=eps() : tolerance parameter for the convex coefficients in λλ.
  • atol_errors=eps(): : tolerance parameter for the linearization errors.
  • bundle_cap=25`
  • m=1e-3: : the parameter to test the decrease of the cost: f(qk+1)≀f(pk)+mΞΎf(q_{k+1}) ≀ f(p_k) + m ΞΎ.
  • 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=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.
  • k_max=0: upper bound on the sectional curvature of the manifold.
  • stepsize=default_stepsize(M, ConvexBundleMethodState): a functor inheriting from Stepsize to determine a step size
  • inverse_retraction_method=default_inverse_retraction_method(M, typeof(p)): an inverse retraction retrβ‘βˆ’1\operatorname{retr}^{-1} to use, see the section on retractions and their inverses* inverse_retraction_method=default_inverse_retraction_method(M, typeof(p)): an inverse retraction retrβ‘βˆ’1\operatorname{retr}^{-1} to use, see the section on retractions and their inverses
  • stopping_criterion=StopWhenLagrangeMultiplierLess(1e-8)|StopAfterIteration(5000): a functor indicating that the stopping criterion is fulfilled
  • vector_transport_method=default_vector_transport_method(M, typeof(p)): a vector transport T⋅←⋅\mathcal T_{⋅←⋅} to use, see the section on vector transports
  • sub_state=convex_bundle_method_subsolver`: a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.
  • sub_problem=AllocatingEvaluation: specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
  • X=zero_vector(M, p): a tangent vector at the point pp on the manifold M\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βˆ—p^*. To obtain the whole final state of the solver, see get_solver_return for details, especially the return_state= keyword.

source

State

Manopt.ConvexBundleMethodState β€” Type
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`

  • 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 retrβ‘βˆ’1\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(qk+1)≀f(pk)+mΞΎf(q_{k+1}) ≀ f(p_k) + m ΞΎ.
  • p::P: a point on the manifold M\mathcal M storing the current iterate
  • p_last_serious::P: last serious iterate
  • retraction_method::AbstractRetractionMethod: a retraction retr⁑\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::AbstractVectorTransportMethodP: a vector transport T⋅←⋅\mathcal T_{⋅←⋅} to use, see the section on vector transports
  • X::T: a tangent vector at the point pp on the manifold M\mathcal Mstoring 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 ΞΎ=βˆ’βˆ₯g∣2–Ρξ = -\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 M\mathcal M
  • sub_problem: specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
  • sub_state: 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.

source

Stopping criteria

Manopt.StopWhenLagrangeMultiplierLess β€” Type
StopWhenLagrangeMultiplierLess <: StoppingCriterion

Stopping Criteria for Lagrange multipliers.

Currently these are meant for the convex_bundle_method and proximal_bundle_method, where based on the Lagrange multipliers an approximate (sub)gradient gg and an error estimate ΡΡ is computed.

The mode=:both requires that both ΡΡ and ∣g∣\lvert g \rvert are smaller than their tolerances for the convex_bundle_method, and that cc and ∣d∣\lvert d \rvert are smaller than their tolerances for the proximal_bundle_method.

The mode=:estimate requires that, for the convex_bundle_method βˆ’ΞΎ=∣g∣2+Ξ΅-ΞΎ = \lvert g \rvert^2 + Ξ΅ is less than a given tolerance. For the proximal_bundle_method, the equation reads βˆ’Ξ½=μ∣d∣2+c-Ξ½ = ΞΌ \lvert d \rvert^2 + c.

Constructors

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

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 ΡΡ (cc), the second the tolerance for ∣g∣\lvert g \rvert (∣d∣\lvert d \rvert), respectively.

source

Debug functions

Manopt.DebugWarnIfLagrangeMultiplierIncreases β€” Type
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.

source

Helpers and internal functions

Manopt.convex_bundle_method_subsolver β€” Function
Ξ» = 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 pkp_k given the current linearization errors cjkc_j^k, and transported subgradients Ppk←qjXqj\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

arg min⁑λ∈R∣Jk∣12βˆ₯βˆ‘j∈JkΞ»jPpk←qjXqjβˆ₯2+βˆ‘j∈JkΞ»j cjks. t.βˆ‘j∈JkΞ»j=1,Ξ»jβ‰₯0for all j∈Jk,\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 Jk={j∈Jkβˆ’1 βˆ£ Ξ»j>0}βˆͺ{k}J_k = \{j ∈ J_{k-1} \ | \ Ξ»_j > 0\} \cup \{k\}. See [BHJ24] for more details

Tip

A default subsolver based on RipQP.jl and QuadraticModels is available if these two packages are loaded.

source
Manopt.DomainBackTrackingStepsize β€” Type
DomainBackTrackingStepsize <: Stepsize

Implement a backtrack as long as we are q=retr⁑p(X)q = \operatorname{retr}_p(X) yields a point closer to pp than βˆ₯Xβˆ₯p\lVert X \rVert_p or qq is not on the domain. For the domain this step size requires a ConvexBundleMethodState.

source
Manopt.DomainBackTracking β€” Function
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): speciy a point to be used as memory for the candidate points.
  • contraction_factor: how to update ss in the decrease step
  • initial_stepsize`: specify an initial step size
  • retraction_method=default_retraction_method(M, typeof(p)): a retraction retr⁑\operatorname{retr} to use, see the section on retractions
Info

This function generates a ManifoldDefaultsFactory for DomainBackTrackingStepsize. For default values, that depend on the manifold, this factory postpones the construction until the manifold from for example a corresponding AbstractManoptSolverState is available.

source
Manopt.estimate_sectional_curvature β€” Function
estimate_sectional_curvature(M::AbstractManifold, p)

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

See also

sectional_curvature

source
Manopt.ΞΆ_1 β€” Function
ΞΆ_1(Ο‰, Ξ΄)

compute a curvature-dependent bound. The formula reads

ΞΆ1,Ο‰(Ξ΄)≔{1if Ο‰β‰₯0,βˆ’Ο‰β€‰Ξ΄cot⁑(βˆ’Ο‰β€‰Ξ΄)if Ο‰<0,\zeta_{1, Ο‰}(Ξ΄) \coloneqq \begin{cases} 1 & \text{if } Ο‰ β‰₯ 0, \\ \sqrt{-Ο‰} \, Ξ΄ \cot(\sqrt{-Ο‰} \, Ξ΄) & \text{if } Ο‰ < 0, \end{cases}

where ω≀κpΟ‰ ≀ ΞΊ_p for all p∈Up ∈ \mathcal U is a lower bound to the sectional curvature in a (strongly geodesically convex) bounded subset UβŠ†M\mathcal U βŠ† \mathcal M with diameter δδ.

source
Manopt.ΞΆ_2 β€” Function
ΞΆ_2(Ξ©, Ξ΄)

compute a curvature-dependent bound. The formula reads

ΞΆ2,Ξ©(Ξ΄)≔{1if Ξ©β‰€0,Ω δcot⁑(Ω δ)if Ξ©>0,\zeta_{2, Ξ©}(Ξ΄) \coloneqq \begin{cases} 1 & \text{if } Ξ© ≀ 0,\\ \sqrt{Ξ©} \, Ξ΄ \cot(\sqrt{Ξ©} \, Ξ΄) & \text{if } Ξ© > 0, \end{cases}

where Ξ©β‰₯ΞΊpΞ© β‰₯ ΞΊ_p for all p∈Up ∈ \mathcal U is an upper bound to the sectional curvature in a (strongly geodesically convex) bounded subset UβŠ†M\mathcal U βŠ† \mathcal M with diameter δδ.

source
Manopt.close_point β€” Function
close_point(M, p, tol; retraction_method=default_retraction_method(M, typeof(p)))

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

source

Literature

[BHJ24]
R. Bergmann, R. Herzog and H. Jasa. The Riemannian Convex Bundle Method, preprint (2024), arXiv:2402.13670.