Mesh adaptive direct search (MADS)

mesh_adaptive_direct_search(M, f, p=rand(M); kwargs...)
mesh_adaptive_direct_search(M, mco::AbstractManifoldCostObjective, p=rand(M); kwargs...)
mesh_adaptive_direct_search!(M, f, p; kwargs...)
mesh_adaptive_direct_search!(M, mco::AbstractManifoldCostObjective, p; kwargs...)

The Mesh Adaptive Direct Search (MADS) algorithm minimizes an objective function $f: \mathcal{M} → ℝ$ on the manifold M. The algorithm constructs an implicit mesh in the tangent space $T_{p}\mathcal{M}$ at the current candidate $p$. Each iteration consists of a search step and a poll step.

The search step selects points from the implicit mesh and attempts to find an improved candidate solution that reduces the value of $f$. If the search step fails to generate an improved candidate solution, the poll step is performed. It consists of a local exploration on the current implicit mesh in the neighborhood of the current iterate.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
• f: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v
• p::P: a point on the manifold $\mathcal{M}$

Keyword arguments

• callbacks::D = Dict{Symbol,Function}(): provided callback functions given either as a single function (symbol, problem, state, k) called in every hook or as a (vector of) pairs :hook => function, which are processed by process_callbacks_arg. As key you can either pass single symbol or an array of symbols to indicate a callback should be added in multiple places
• max_stepsize=injectivity_radius(M): a maximum step size to take, where 1.0 is used if the injectivity radius is infinite. Any vector generated on the mesh is shortened to this length to avoid leaving the injectivity radius.
• mesh_basis=default_basis(M, typeof(p)): a basis to generate the mesh in. The mesh is generated in coordinates of this basis in every tangent space
• poll::AbstractMeshPollFunction=LowerTriangularAdaptivePoll(M, copy(M,p)): the poll function to use. The mesh_basis (as basis), retraction_method, and vector_transport_method are passed to this default as well.
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• scale_mesh=injectivity_radius(M) / 4: initial scaling of the mesh, where 1.0 is used if the injectivity radius is infinite
• search::AbstractMeshSearchFunction=DefaultMeshAdaptiveDirectSearch(M, copy(M,p)): the search function to use. The retraction_method is passed to this default as well.
• stopping_criterion::StoppingCriterion=StopAfterIteration(500)|StopWhenPollSizeLess(1e-10): a functor indicating that the stopping criterion is fulfilled
• vector_transport_method::AbstractVectorTransportMethod=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.

mesh_adaptive_direct_search(M, f, p=rand(M); kwargs...)
mesh_adaptive_direct_search(M, mco::AbstractManifoldCostObjective, p=rand(M); kwargs...)
mesh_adaptive_direct_search!(M, f, p; kwargs...)
mesh_adaptive_direct_search!(M, mco::AbstractManifoldCostObjective, p; kwargs...)

The Mesh Adaptive Direct Search (MADS) algorithm minimizes an objective function $f: \mathcal{M} → ℝ$ on the manifold M. The algorithm constructs an implicit mesh in the tangent space $T_{p}\mathcal{M}$ at the current candidate $p$. Each iteration consists of a search step and a poll step.

The search step selects points from the implicit mesh and attempts to find an improved candidate solution that reduces the value of $f$. If the search step fails to generate an improved candidate solution, the poll step is performed. It consists of a local exploration on the current implicit mesh in the neighborhood of the current iterate.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
• f: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v
• p::P: a point on the manifold $\mathcal{M}$

Keyword arguments

• callbacks::D = Dict{Symbol,Function}(): provided callback functions given either as a single function (symbol, problem, state, k) called in every hook or as a (vector of) pairs :hook => function, which are processed by process_callbacks_arg. As key you can either pass single symbol or an array of symbols to indicate a callback should be added in multiple places
• max_stepsize=injectivity_radius(M): a maximum step size to take, where 1.0 is used if the injectivity radius is infinite. Any vector generated on the mesh is shortened to this length to avoid leaving the injectivity radius.
• mesh_basis=default_basis(M, typeof(p)): a basis to generate the mesh in. The mesh is generated in coordinates of this basis in every tangent space
• poll::AbstractMeshPollFunction=LowerTriangularAdaptivePoll(M, copy(M,p)): the poll function to use. The mesh_basis (as basis), retraction_method, and vector_transport_method are passed to this default as well.
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• scale_mesh=injectivity_radius(M) / 4: initial scaling of the mesh, where 1.0 is used if the injectivity radius is infinite
• search::AbstractMeshSearchFunction=DefaultMeshAdaptiveDirectSearch(M, copy(M,p)): the search function to use. The retraction_method is passed to this default as well.
• stopping_criterion::StoppingCriterion=StopAfterIteration(500)|StopWhenPollSizeLess(1e-10): a functor indicating that the stopping criterion is fulfilled
• vector_transport_method::AbstractVectorTransportMethod=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.

MeshAdaptiveDirectSearchState <: AbstractManoptSolverState

Fields

• callbacks::D: provided callback functions given as a dictionary with symbols as keys
• p::P: a point on the manifold $\mathcal{M}$ storing the current iterate
• mesh_size: the current (internal) mesh size
• scale_mesh: the current scaling of the internal mesh size, yields the actual mesh size used
• max_stepsize: an upper bound for the longest step taken in looking for a candidate in either poll or search
• poll_size: the current poll size, in each iteration set to manifold_dimension(M) * sqrt(mesh_size)
• stop::StoppingCriterion: a functor indicating that the stopping criterion is fulfilled
• poll::AbstractMeshPollFunction: a poll step (functor) to perform
• search::AbstractMeshSearchFunction: a search step (functor) to perform

Constructor

MeshAdaptiveDirectSearchState(M::AbstractManifold, p=rand(M); kwargs...)

Keyword arguments

• callbacks::D = Dict{Symbol,Function}(): provided callback functions given as a dictionary with symbols as keys
• max_stepsize=injectivity_radius(M): a maximum step size, where 1.0 is used if the injectivity radius is infinite
• mesh_basis=default_basis(M, typeof(p)): a basis to generate the mesh in
• poll::AbstractMeshPollFunction=LowerTriangularAdaptivePoll(M, copy(M,p)): the poll function to use
• poll_size=manifold_dimension(M): the initial poll size
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• scale_mesh=injectivity_radius(M) / 4: initial scaling of the mesh, where 1.0 is used if the injectivity radius is infinite
• search::AbstractMeshSearchFunction=DefaultMeshAdaptiveDirectSearch(M, copy(M,p)): the search function to use
• stopping_criterion::StoppingCriterion=StopAfterIteration(500)|StopWhenPollSizeLess(1e-10): a functor indicating that the stopping criterion is fulfilled
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

AbstractMeshPollFunction

An abstract type for common “poll” strategies in the mesh_adaptive_direct_search solver. A subtype of this has to fulfill

• be callable as poll!(problem, mesh_size; kwargs...) and modify the state

as well as to provide functions

• is_successful(poll!) that indicates whether the last poll was successful in finding a new candidate
• get_basepoint(poll!) that returns the base point at which the mesh is built
• get_candidate(poll!) that returns the last found candidate if the poll was successful. Otherwise the base point is returned
• get_descent_direction(poll!) that returns the vector that points from the base point to the candidate. If the last poll was not successful, the zero vector is returned
• update_basepoint!(M, poll!, p) that updates the base point to p and all necessary internal data to a new point to build a mesh at

The kwargs... could include

• scale_mesh=1.0: to rescale the mesh globally
• max_stepsize=Inf: avoid exceeding a step size beyond this value, e.g. injectivity radius. Any vector longer than this should be shortened to the provided maximum step size.

LowerTriangularAdaptivePoll <: AbstractMeshPollFunction

Generate a mesh (poll step) based on Section 6 and 7 of [Dre07], with two small modifications:

• The mesh can be scaled globally so instead of $Δ_0^m=1$ a certain different scale is used
• Any poll direction can be rescaled if it is too long. This is to not exceed the injectivity radius for example.

Function

(ltap::LowerTriangularAdaptivePoll)(problem, mesh_size; scale_mesh=1.0, max_stepsize=Inf)

Fields

• base_point::P: a point on the manifold, where the mesh is built in the tangent space
• basis: a basis of the current tangent space with respect to which the mesh is stored
• candidate::P: a memory for a new point/candidate
• last_poll_improved::Bool: whether the last poll found a candidate with a smaller cost
• mesh: a matrix whose columns are the coordinates, with respect to basis, of the mesh directions in the tangent space at base_point.
• random_vector: a $d$-dimensional random vector $b_l$
• random_index: a random index $ι$
• poll_counter: the mesh level $l$ the stored random_vector and random_index were generated for
• retraction_method::AbstractRetractionMethod: a retraction $\operatorname{retr}$ to use, see the section on retractions
• vector_transport_method::AbstractVectorTransportMethod: a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• X::T: the last successful poll direction stored as a tangent vector. Initialized to the zero vector, transported to the new tangent space when the base point is updated, and reset to the zero vector after an unsuccessful poll.

Constructor

LowerTriangularAdaptivePoll(M, p=rand(M); kwargs...)

Keyword arguments

• basis=default_basis(M, typeof(p)): a basis for the tangent space
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• X::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$

get_descent_direction(ltap::LowerTriangularAdaptivePoll)

Return the direction of the last LowerTriangularAdaptivePoll that yields a descent of the cost. If the poll was not successful, the zero vector is returned

is_successful(ltap::LowerTriangularAdaptivePoll)

Return whether the last LowerTriangularAdaptivePoll step was successful

get_candidate(ltap::LowerTriangularAdaptivePoll)

Return the candidate of the last successful LowerTriangularAdaptivePoll. If the poll was unsuccessful, the base point is returned.

get_basepoint(ltap::LowerTriangularAdaptivePoll)

Return the base point of the tangent space in which the mesh for the LowerTriangularAdaptivePoll is built.

update_basepoint!(M, ltap::LowerTriangularAdaptivePoll, p)

Update the base point of the LowerTriangularAdaptivePoll. This especially also updates the basis, that is used to build a (new) mesh.

AbstractMeshSearchFunction

Should be callable as search!(problem, mesh_size, p, X; kwargs...)

where X is the last successful poll direction from the tangent space at p if that exists and the zero vector otherwise.

Besides that the following functions should be implemented

• is_successful(search!) that indicates whether the last search was successful in finding a new candidate
• get_candidate(search!) that returns the last found candidate

DefaultMeshAdaptiveDirectSearch <: AbstractMeshSearchFunction

Function

(s::DefaultMeshAdaptiveDirectSearch)(problem, mesh_size::Real, p, X; scale_mesh::Real=1.0, max_stepsize::Real=Inf)

Fields

• p: the candidate of the last successful search, returned by get_candidate
• q: a temporary memory for a point on the manifold
• X: information to perform the search, e.g. the last direction found by poll.
• last_search_improved::Bool: indicates whether the last search was successful, i.e. improved the cost.
• retraction_method::AbstractRetractionMethod: a retraction $\operatorname{retr}$ to use, see the section on retractions

Constructor

DefaultMeshAdaptiveDirectSearch(M::AbstractManifold, p=rand(M); kwargs...)

Keyword arguments

• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• X::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$

is_successful(dmads::DefaultMeshAdaptiveDirectSearch)

Return whether the last DefaultMeshAdaptiveDirectSearch was successful.

get_candidate(dmads::DefaultMeshAdaptiveDirectSearch)

Return the last candidate a DefaultMeshAdaptiveDirectSearch found

StopWhenPollSizeLess <: StoppingCriterion

stores a threshold when to stop looking at the poll mesh size of a MeshAdaptiveDirectSearchState.

Constructor

StopWhenPollSizeLess(ε)

initialize the stopping criterion to a threshold ε.