Proximal bundle method

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

• α₀=1.2: initialization value for α, used to update η
• bundle_size=50: the maximal size of the bundle
• δ=1.0: parameter for updating μ: if $δ < 0$ then $μ = \log(i + 1)$, else $μ += δ μ$
• ε=1e-2: stepsize-like parameter related to the injectivity radius of the manifold
• 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.
• inverse_retraction_method=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• m=0.0125: a real number that controls the decrease of the cost function
• μ=0.5: initial proximal parameter for the subproblem
• retraction_method=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stopping_criterion=StopWhenLagrangeMultiplierLess(1e-8)|StopAfterIteration(5000): a functor indicating that the stopping criterion is fulfilled
• sub_problem=proximal_bundle_method_subsolver`: specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
• sub_state=AllocatingEvaluation: a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.
• vector_transport_method=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

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.

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

• α₀=1.2: initialization value for α, used to update η
• bundle_size=50: the maximal size of the bundle
• δ=1.0: parameter for updating μ: if $δ < 0$ then $μ = \log(i + 1)$, else $μ += δ μ$
• ε=1e-2: stepsize-like parameter related to the injectivity radius of the manifold
• 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.
• inverse_retraction_method=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• m=0.0125: a real number that controls the decrease of the cost function
• μ=0.5: initial proximal parameter for the subproblem
• retraction_method=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stopping_criterion=StopWhenLagrangeMultiplierLess(1e-8)|StopAfterIteration(5000): a functor indicating that the stopping criterion is fulfilled
• sub_problem=proximal_bundle_method_subsolver`: specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
• sub_state=AllocatingEvaluation: a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.
• vector_transport_method=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

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.

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

• α₀=1.2
• bundle_size=50
• δ=1.0
• ε=1e-2
• μ=0.5
• m=0.0125
• retraction_method=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• inverse_retraction_method=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• p=rand(M): a point on the manifold $\mathcal M$to specify the initial value
• stopping_criterion=StopWhenLagrangeMultiplierLess(1e-8)|StopAfterIteration(5000): a functor indicating that the stopping criterion is fulfilled
• sub_problem=proximal_bundle_method_subsolver`: specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
• sub_state=AllocatingEvaluation: a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.
• vector_transport_method=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• X=zero_vector(M, p) 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].