Convex bundle method
Manopt.convex_bundle_method
β Functionconvex_bundle_method(M, f, βf, p)
convex_bundle_method!(M, f, βf, p)
perform a convex bundle method where
and is the last serious iterate, , and the 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
f
: a cost function 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
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: .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 objectivef
, 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 fromStepsize
to determine a step sizeinverse_retraction_method=
default_inverse_retraction_method
(M, typeof(p))
: an inverse retraction to use, see the section on retractions and their inverses*inverse_retraction_method=
default_inverse_retraction_method
(M, typeof(p))
: an inverse retraction to use, see the section on retractions and their inversesstopping_criterion=
StopWhenLagrangeMultiplierLess
(1e-8)
|
StopAfterIteration
(5000)
: a functor indicating that the stopping criterion is fulfilledvector_transport_method=
default_vector_transport_method
(M, typeof(p))
: a vector transport to use, see the section on vector transportssub_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 on the manifold
All other keyword arguments are passed to decorate_state!
for state decorators or decorate_objective!
for objective decorators, respectively.
Output
The obtained approximate minimizer . To obtain the whole final state of the solver, see get_solver_return
for details, especially the return_state=
keyword.
Manopt.convex_bundle_method!
β Functionconvex_bundle_method(M, f, βf, p)
convex_bundle_method!(M, f, βf, p)
perform a convex bundle method where
and is the last serious iterate, , and the 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
f
: a cost function 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
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: .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 objectivef
, 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 fromStepsize
to determine a step sizeinverse_retraction_method=
default_inverse_retraction_method
(M, typeof(p))
: an inverse retraction to use, see the section on retractions and their inverses*inverse_retraction_method=
default_inverse_retraction_method
(M, typeof(p))
: an inverse retraction to use, see the section on retractions and their inversesstopping_criterion=
StopWhenLagrangeMultiplierLess
(1e-8)
|
StopAfterIteration
(5000)
: a functor indicating that the stopping criterion is fulfilledvector_transport_method=
default_vector_transport_method
(M, typeof(p))
: a vector transport to use, see the section on vector transportssub_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 on the manifold
All other keyword arguments are passed to decorate_state!
for state decorators or decorate_objective!
for objective decorators, respectively.
Output
The obtained approximate minimizer . To obtain the whole final state of the solver, see get_solver_return
for details, especially the return_state=
keyword.
State
Manopt.ConvexBundleMethodState
β TypeConvexBundleMethodState <: 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 iteratebundle_cap::Int
: the maximal number of elements the bundle is allowed to rememberdiameter::R
: estimate for the diameter of the level set of the objective function at the starting pointdomain: the domain of
f
as a function
(M,p) -> bthat evaluates to true when the current candidate is in the domain of
f`, and false otherwise,g::T
: descent directioninverse_retraction_method::AbstractInverseRetractionMethod
: an inverse retraction to use, see the section on retractions and their inversesk_max::R
: upper bound on the sectional curvature of the manifoldlinearization_errors<:AbstractVector{<:R}
: linearization errors at the last serious stepm::R
: the parameter to test the decrease of the cost: .p::P
: a point on the manifold storing the current iteratep_last_serious::P
: last serious iterateretraction_method::AbstractRetractionMethod
: a retraction to use, see the section on retractionsstop::StoppingCriterion
: a functor indicating that the stopping criterion is fulfilledtransported_subgradients
: subgradients of the bundle that are transported top_last_serious
vector_transport_method::AbstractVectorTransportMethodP
: a vector transport to use, see the section on vector transportsX::T
: a tangent vector at the point on the manifold storing a subgradient at the current iteratestepsize::Stepsize
: a functor inheriting fromStepsize
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 bysub_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
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.
atol_Ξ»=eps()
atol_errors=eps()
bundle_cap=25
`m=1e-2
diameter=50.0
domain=(M, p) -> isfinite(f(M, p))
k_max=0
k_min=0
p=
rand
(M)
: a point on the manifold to specify the initial valuestepsize=
default_stepsize
(M, ConvexBundleMethodState)
: a functor inheriting fromStepsize
to determine a step sizeinverse_retraction_method=
default_inverse_retraction_method
(M, typeof(p))
: an inverse retraction to use, see the section on retractions and their inversesretraction_method=
default_retraction_method
(M, typeof(p))
: a retraction to use, see the section on retractionsstopping_criterion=
StopWhenLagrangeMultiplierLess
(1e-8)
|
StopAfterIteration
(5000)
: a functor indicating that the stopping criterion is fulfilledX=
zero_vector
(M, p)
specify the type of tangent vector to use.vector_transport_method=
default_vector_transport_method
(M, typeof(p))
: a vector transport to use, see the section on vector transports
Stopping criteria
Manopt.StopWhenLagrangeMultiplierLess
β TypeStopWhenLagrangeMultiplierLess <: 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 and an error estimate is computed.
The mode=:both
requires that both and are smaller than their tolerance
s for the convex_bundle_method
, and that and are smaller than their tolerance
s for the proximal_bundle_method
.
The mode=:estimate
requires that, for the convex_bundle_method
is less than a given tolerance
. For the proximal_bundle_method
, the equation reads .
Constructors
StopWhenLagrangeMultiplierLess(tolerance=1e-6; mode::Symbol=:estimate, names=nothing)
Create the stopping criterion for one of the mode
s 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 (), the second the tolerance for (), respectively.
Debug functions
Manopt.DebugWarnIfLagrangeMultiplierIncreases
β TypeDebugWarnIfLagrangeMultiplierIncreases <: 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
.
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 given the current linearization errors , and transported subgradients .
The computation can also be done in-place of Ξ»
.
The subproblem for the convex bundle method is
where . See [BHJ24] for more details
A default subsolver based on RipQP
.jl and QuadraticModels
is available if these two packages are loaded.
Manopt.DomainBackTrackingStepsize
β TypeDomainBackTrackingStepsize <: Stepsize
Implement a backtrack as long as we are yields a point closer to than or is not on the domain. For the domain this step size requires a ConvexBundleMethodState
.
Manopt.DomainBackTracking
β FunctionDomainBackTracking(; 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 in the decrease stepinitial_stepsize
`: specify an initial step sizeretraction_method=
default_retraction_method
(M, typeof(p))
: a retraction to use, see the section on retractions
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.
Manopt.NullStepBackTrackingStepsize
β TypeNullStepBackTrackingStepsize <: Stepsize
Implement a backtracking with a geometric condition in the case of a null step. For the domain this step size requires a ConvexBundleMethodState
.
Manopt.estimate_sectional_curvature
β Functionestimate_sectional_curvature(M::AbstractManifold, p)
Estimate the sectional curvature of a manifold at a point on two random tangent vectors at that are orthogonal to each other.
See also
Manopt.ΞΆ_1
β FunctionΞΆ_1(Ο, Ξ΄)
compute a curvature-dependent bound. The formula reads
where for all is a lower bound to the sectional curvature in a (strongly geodesically convex) bounded subset with diameter .
Manopt.ΞΆ_2
β FunctionΞΆ_2(Ξ©, Ξ΄)
compute a curvature-dependent bound. The formula reads
where for all is an upper bound to the sectional curvature in a (strongly geodesically convex) bounded subset with diameter .
Manopt.close_point
β Functionclose_point(M, p, tol; retraction_method=default_retraction_method(M, typeof(p)))
sample a random point close to within a tolerance tol
and a retraction.
Literature
- [BHJ24]
- R. Bergmann, R. Herzog and H. Jasa. The Riemannian Convex Bundle Method, preprint (2024), arXiv:2402.13670.