# Proximal bundle method

Manopt.proximal_bundle_methodFunction
proximal_bundle_method(M, f, ∂f, p=rand(M), kwargs...)
proximal_bundle_method!(M, f, ∂f, p, kwargs...)

perform a proximal bundle method $p^{(k+1)} = \operatorname{retr}_{p^{(k)}}(-d_k)$, where $\operatorname{retr}$ is a retraction and

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

with $X_{q_j} ∈ ∂f(q_j)$, $p_k$ the last serious iterate, $\mu_k$ a proximal parameter, and the $λ_j^k$ as solutions to the quadratic subproblem provided by the sub solver, see for example 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].

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal M$
• f: a cost function $f: \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 $\mathcal M$

Keyword arguments

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.

source
Manopt.proximal_bundle_method!Function
proximal_bundle_method(M, f, ∂f, p=rand(M), kwargs...)
proximal_bundle_method!(M, f, ∂f, p, kwargs...)

perform a proximal bundle method $p^{(k+1)} = \operatorname{retr}_{p^{(k)}}(-d_k)$, where $\operatorname{retr}$ is a retraction and

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

with $X_{q_j} ∈ ∂f(q_j)$, $p_k$ the last serious iterate, $\mu_k$ a proximal parameter, and the $λ_j^k$ as solutions to the quadratic subproblem provided by the sub solver, see for example 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].

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal M$
• f: a cost function $f: \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 $\mathcal M$

Keyword arguments

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.

source

## State

Manopt.ProximalBundleMethodStateType
ProximalBundleMethodState <: AbstractManoptSolverState

stores option values for a proximal_bundle_method solver.

Fields

• α: curvature-dependent parameter used to update η
• α₀: initialization value for α, used to update η
• 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: the maximal size of the bundle
• c: convex combination of the approximation errors
• d: descent direction
• δ: parameter for updating μ: if $δ < 0$ then $μ = \log(i + 1)$, else $μ += δ μ$
• ε: stepsize-like parameter related to the injectivity radius of the manifold
• η: curvature-dependent term for updating the approximation errors
• inverse_retraction_method::AbstractInverseRetractionMethod: an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• λ: convex coefficients that solve the subproblem
• m: the parameter to test the decrease of the cost
• μ: (initial) proximal parameter for the subproblem
• ν: the stopping parameter given by $ν = - μ |d|^2 - c$
• p::P: a point on the manifold $\mathcal M$storing the current iterate
• p_last_serious: 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::AbstractVectorTransportMethodP: 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
• 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

ProximalBundleMethodState(M::AbstractManifold, sub_problem, sub_state; kwargs...)
ProximalBundleMethodState(M::AbstractManifold, sub_problem=proximal_bundle_method_subsolver; evaluation=AllocatingEvaluation(), kwargs...)

Generate the state for the proximal_bundle_method on the manifold M

Keyword arguments

source

## Helpers and internal functions

Manopt.proximal_bundle_method_subsolverFunction
λ = 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].

Tip

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

source

## Literature

[HNP23]
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).