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 solutions to 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].

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

Optional

• 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, that is it 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.

Output

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

Input

• 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.

Fields

• 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 p_last_serious
• 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) initialization 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,
• sub_state: an AbstractManoptSolverState for the subsolver

Constructor

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

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

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