Nelder-Mead method

NelderMead(M::AbstractManifold, f, population=NelderMeadSimplex(M))
NelderMead(M::AbstractManifold, mco::AbstractManifoldCostObjective, population=NelderMeadSimplex(M))
NelderMead!(M::AbstractManifold, f, population)
NelderMead!(M::AbstractManifold, mco::AbstractManifoldCostObjective, population)

Solve a Nelder-Mead minimization problem for the cost function $f: \mathcal{M} → ℝ$ on the manifold M. If the initial NelderMeadSimplex is not provided, a random set of points is chosen. The computation can be performed in-place of the population.

The algorithm consists of the following steps. Let $d$ denote the dimension of the manifold $\mathcal{M}$.

1. Order the simplex vertices $p_i, i=1,…,d+1$ by increasing cost, such that we have $f(p_1) ≤ f(p_2) ≤ … ≤ f(p_{d+1})$.
2. Compute the Riemannian center of mass [Kar77], cf. mean, $p_{\text{m}}$ of the simplex vertices $p_1,…,p_{d}$, that is, of all but the worst point.
3. Reflect the worst point at the mean $p_{\text{r}} = \operatorname{retr}_{p_{\text{m}}}\bigl( - α\operatorname{retr}^{-1}_{p_{\text{m}}} (p_{d+1}) \bigr)$ If $f(p_1) ≤ f(p_{\text{r}}) ≤ f(p_{d})$ then set $p_{d+1} = p_{\text{r}}$ and go to step 1.
4. Expand the simplex if $f(p_{\text{r}}) < f(p_1)$ by computing the expansion point $p_{\text{e}} = \operatorname{retr}_{p_{\text{m}}}\bigl( - γα\operatorname{retr}^{-1}_{p_{\text{m}}} (p_{d+1}) \bigr)$, which in this formulation allows to reuse the tangent vector from the inverse retraction from before. If $f(p_{\text{e}}) < f(p_{\text{r}})$ then set $p_{d+1} = p_{\text{e}}$ otherwise set $p_{d+1} = p_{\text{r}}$. Then go to Step 1.
5. Contract the simplex if $f(p_{\text{r}}) > f(p_d)$. Set the step $s = -ρ$ if $f(p_{\text{r}}) < f(p_{d+1})$ and $s = ρ$ otherwise. Compute the contraction point $p_{\text{c}} = \operatorname{retr}_{p_{\text{m}}}\bigl(s\operatorname{retr}^{-1}_{p_{\text{m}}} p_{d+1} \bigr)$. If $f(p_{\text{c}}) < f(p_{d+1})$ set $p_{d+1} = p_{\text{c}}$ and go to step 1, otherwise continue with step 6.
6. Shrink all points (closer to $p_1$). For all $i=2,...,d+1$ set $p_{i} = \operatorname{retr}_{p_{1}}\bigl( σ\operatorname{retr}^{-1}_{p_{1}} p_{i} \bigr).$

For more details, see the Euclidean variant in the Wikipedia https://en.wikipedia.org/wiki/Nelder-Mead_method or Algorithm 4.1 in http://www.optimization-online.org/DB_FILE/2007/08/1742.pdf.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
• f: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v
• population::NelderMeadSimplex=NelderMeadSimplex(M): an initial simplex of $d+1$ points, where $d$ is the manifold_dimension of 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
• inverse_retraction_method::AbstractInverseRetractionMethod=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stopping_criterion::StoppingCriterion=StopAfterIteration(2000)|StopWhenPopulationConcentrated(): a functor indicating that the stopping criterion is fulfilled
• α=1.0: reflection parameter, $α > 0$
• γ=2.0: expansion parameter, $γ > 1$
• ρ=1/2: contraction parameter, $0 < ρ ≤ \frac{1}{2}$,
• σ=1/2: shrink coefficient, $0 < σ ≤ 1$

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.

NelderMead(M::AbstractManifold, f, population=NelderMeadSimplex(M))
NelderMead(M::AbstractManifold, mco::AbstractManifoldCostObjective, population=NelderMeadSimplex(M))
NelderMead!(M::AbstractManifold, f, population)
NelderMead!(M::AbstractManifold, mco::AbstractManifoldCostObjective, population)

Solve a Nelder-Mead minimization problem for the cost function $f: \mathcal{M} → ℝ$ on the manifold M. If the initial NelderMeadSimplex is not provided, a random set of points is chosen. The computation can be performed in-place of the population.

The algorithm consists of the following steps. Let $d$ denote the dimension of the manifold $\mathcal{M}$.

1. Order the simplex vertices $p_i, i=1,…,d+1$ by increasing cost, such that we have $f(p_1) ≤ f(p_2) ≤ … ≤ f(p_{d+1})$.
2. Compute the Riemannian center of mass [Kar77], cf. mean, $p_{\text{m}}$ of the simplex vertices $p_1,…,p_{d}$, that is, of all but the worst point.
3. Reflect the worst point at the mean $p_{\text{r}} = \operatorname{retr}_{p_{\text{m}}}\bigl( - α\operatorname{retr}^{-1}_{p_{\text{m}}} (p_{d+1}) \bigr)$ If $f(p_1) ≤ f(p_{\text{r}}) ≤ f(p_{d})$ then set $p_{d+1} = p_{\text{r}}$ and go to step 1.
4. Expand the simplex if $f(p_{\text{r}}) < f(p_1)$ by computing the expansion point $p_{\text{e}} = \operatorname{retr}_{p_{\text{m}}}\bigl( - γα\operatorname{retr}^{-1}_{p_{\text{m}}} (p_{d+1}) \bigr)$, which in this formulation allows to reuse the tangent vector from the inverse retraction from before. If $f(p_{\text{e}}) < f(p_{\text{r}})$ then set $p_{d+1} = p_{\text{e}}$ otherwise set $p_{d+1} = p_{\text{r}}$. Then go to Step 1.
5. Contract the simplex if $f(p_{\text{r}}) > f(p_d)$. Set the step $s = -ρ$ if $f(p_{\text{r}}) < f(p_{d+1})$ and $s = ρ$ otherwise. Compute the contraction point $p_{\text{c}} = \operatorname{retr}_{p_{\text{m}}}\bigl(s\operatorname{retr}^{-1}_{p_{\text{m}}} p_{d+1} \bigr)$. If $f(p_{\text{c}}) < f(p_{d+1})$ set $p_{d+1} = p_{\text{c}}$ and go to step 1, otherwise continue with step 6.
6. Shrink all points (closer to $p_1$). For all $i=2,...,d+1$ set $p_{i} = \operatorname{retr}_{p_{1}}\bigl( σ\operatorname{retr}^{-1}_{p_{1}} p_{i} \bigr).$

For more details, see the Euclidean variant in the Wikipedia https://en.wikipedia.org/wiki/Nelder-Mead_method or Algorithm 4.1 in http://www.optimization-online.org/DB_FILE/2007/08/1742.pdf.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
• f: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v
• population::NelderMeadSimplex=NelderMeadSimplex(M): an initial simplex of $d+1$ points, where $d$ is the manifold_dimension of 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
• inverse_retraction_method::AbstractInverseRetractionMethod=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stopping_criterion::StoppingCriterion=StopAfterIteration(2000)|StopWhenPopulationConcentrated(): a functor indicating that the stopping criterion is fulfilled
• α=1.0: reflection parameter, $α > 0$
• γ=2.0: expansion parameter, $γ > 1$
• ρ=1/2: contraction parameter, $0 < ρ ≤ \frac{1}{2}$,
• σ=1/2: shrink coefficient, $0 < σ ≤ 1$

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.

NelderMeadState <: AbstractManoptSolverState

Describes all parameters and the state of a Nelder-Mead heuristic based optimization algorithm.

Fields

The naming of these parameters follows the Wikipedia article of the Euclidean case; the required value range is given after the description.

• callbacks::D: provided callback functions given as a dictionary with symbols as keys
• costs: the cost values of the population points, in the same order
• stop::StoppingCriterion: a functor indicating that the stopping criterion is fulfilled
• population::NelderMeadSimplex: a population (set) of $d+1$ points $p_i$, $i=1,…,d+1$, where $d$ is the manifold_dimension of M.
• α: the reflection parameter $α > 0$,
• γ: the expansion parameter $γ > 1$,
• ρ: the contraction parameter, $0 < ρ ≤ \frac{1}{2}$,
• σ: the shrinkage coefficient, $0 < σ ≤ 1$
• p::P: a point on the manifold $\mathcal{M}$ storing the current best point
• inverse_retraction_method::AbstractInverseRetractionMethod: an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• retraction_method::AbstractRetractionMethod: a retraction $\operatorname{retr}$ to use, see the section on retractions

Constructors

NelderMeadState(M::AbstractManifold; kwargs...)

Construct a Nelder-Mead state with a default population (if not provided) of manifold_dimension(M)+1 random points stored in NelderMeadSimplex.

Keyword arguments

• callbacks::D = Dict{Symbol,Function}(): provided callback functions given as a dictionary with symbols as keys
• inverse_retraction_method::AbstractInverseRetractionMethod=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• p=copy(M, population.pts[1]): initialize the storage for the best point (iterate)
• population=NelderMeadSimplex(M)
• stopping_criterion::StoppingCriterion=StopAfterIteration(2000)|StopWhenPopulationConcentrated(): a functor indicating that the stopping criterion is fulfilled
• α=1.0: reflection parameter, $α > 0$
• γ=2.0: expansion parameter, $γ > 1$
• ρ=1/2: contraction parameter, $0 < ρ ≤ \frac{1}{2}$,
• σ=1/2: shrink coefficient, $0 < σ ≤ 1$

NelderMeadSimplex

A simplex for the Nelder-Mead algorithm.

Constructors

NelderMeadSimplex(M::AbstractManifold)

Construct a simplex using $d+1$ random points from manifold M, where $d$ is the manifold_dimension of M.

NelderMeadSimplex(    M::AbstractManifold,    p,    B::AbstractBasis=default_basis(M, typeof(p));    a::Real=0.025,    retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)),)

Construct a simplex from a basis B with one point being p and other points constructed by moving by a in each principal direction defined by basis B of the tangent space at point p using retraction retraction_method. This works similarly to how the initial simplex is constructed in the Euclidean Nelder-Mead algorithm, just in the tangent space at point p.

StopWhenPopulationConcentrated <: StoppingCriterion

A stopping criterion for NelderMead to indicate to stop when both

• the maximal distance of the first to the remaining cost values and
• the maximal distance of the first to the remaining population points

drops below a certain tolerance tol_f and tol_p, respectively.

Constructor

StopWhenPopulationConcentrated(tol_f::Real=1e-8, tol_p::Real=1e-8)