Proximal Bundle Method

proximal_bundle_method(M, f, ∂f, p)

perform a proximal bundle method $p_{j+1} = \mathrm{retr}(p_k, -d_k)$, where

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

where $X_{q_j}\in∂f(q_j)$, $\mathrm{retr}$ is a retraction, $p_k$ is the last serious iterate, $\mu_l$ is a proximal parameter, and the $λ_j^k$ are solutionsto the quadratic subproblem provided by the proximal_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 [HNP23].


  • 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 ∈ \mathcal M$


  • m: a real number that controls the decrease of the cost function
  • 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 – (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

... and the ones that are passed to decorate_state! for decorators.


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

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

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


  • M – a manifold $\mathcal M$
  • f – a cost function $f:\mathcal M→ℝ$ to minimize
  • ∂f- the (sub)gradient $\partial 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 proximal_bundle_method.



ProximalBundleMethodState <: AbstractManoptSolverState

stores option values for a proximal_bundle_method solver.


  • approx_errors: approximation of the linearization errors at the last serious step
  • bundle: bundle that collects each iterate with the computed subgradient at the iterate
  • bundle_size: (50) the maximal size of the bundle
  • c: convex combination of the approximation errors
  • d: descent direction
  • inverse_retraction_method: the inverse retraction to use within
  • m: (0.0125) the parameter to test the decrease of the cost
  • 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.
  • α₀: (1.2) initalization value for α, used to update η
  • α: curvature-dependent parameter used to update η
  • ε: (1e-2) stepsize-like parameter related to the injectivity radius of the manifold
  • δ: parameter for updating μ: if $δ < 0$ then $μ = \log(i + 1)$, else $μ += δ μ$
  • η: curvature-dependent term for updating the approximation errors
  • λ: convex coefficients that solve the subproblem
  • μ: (0.5) (initial) proximal parameter for the subproblem
  • ν: the stopping parameter given by $ν = - μ |d|^2 - c$
  • 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,


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

with keywords for all fields above 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


Helpers and internal functions

λ = proximal_bundle_method_subsolver(M, p_last_serious, μ, approximation_errors, transported_subgradients)
proximal_bundle_method_subsolver!(M, λ, p_last_serious, μ, approximation_errors, transported_subgradients)

solver for the subproblem of the proximal bundle method.

The subproblem for the proximal bundle method is

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

where $L_l = \{k\}$ if $q_k$ is a serious iterate, and $L_l = L_{l-1} \cup \{k\}$ otherwise. See [HNP23].


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



N. Hoseini Monjezi, S. Nobakhtian and M. R. Pouryayevali. A proximal bundle algorithm for nonsmooth optimization on Riemannian manifolds. IMA Journal of Numerical Analysis 43, 293–325 (2023).