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 compuation 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+1}$.
3. Reflect the point with 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 expantion 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 set $p_{d+1} = p_{\text{r}}$. Then go to Step 1.
5. Contract the simplex if $f(p_{\text{r}}) ≥ f(p_d)$.
1. If $f(p_{\text{r}}) < f(p_{d+1})$ set the step $s = -ρ$
2. otherwise set $s=ρ$.
Compute the contraction point $p_{\text{c}} = \operatorname{retr}_{p_{\text{m}}}\bigl(s\operatorname{retr}^{-1}_{p_{\text{m}}} p_{d+1} \bigr)$.
1. in this case if $f(p_{\text{c}}) < f(p_{\text{r}})$ set $p_{d+1} = p_{\text{c}}$ and go to step 1
2. in this case if $f(p_{\text{c}}) < f(p_{d+1})$ set $p_{d+1} = p_{\text{c}}$ and go to step 1
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

Keyword arguments

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.

source

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 compuation 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+1}$.
3. Reflect the point with 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 expantion 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 set $p_{d+1} = p_{\text{r}}$. Then go to Step 1.
5. Contract the simplex if $f(p_{\text{r}}) ≥ f(p_d)$.
1. If $f(p_{\text{r}}) < f(p_{d+1})$ set the step $s = -ρ$
2. otherwise set $s=ρ$.
Compute the contraction point $p_{\text{c}} = \operatorname{retr}_{p_{\text{m}}}\bigl(s\operatorname{retr}^{-1}_{p_{\text{m}}} p_{d+1} \bigr)$.
1. in this case if $f(p_{\text{c}}) < f(p_{\text{r}})$ set $p_{d+1} = p_{\text{c}}$ and go to step 1
2. in this case if $f(p_{\text{c}}) < f(p_{d+1})$ set $p_{d+1} = p_{\text{c}}$ and go to step 1
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

Keyword arguments

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.

source

## State

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 default is given in brackets, the required value range after the description

• population::NelderMeadSimplex: a population (set) of $d+1$ points $x_i$, $i=1,…,n+1$, where $d$ is the manifold_dimension of M.
• stepsize::Stepsize: a functor inheriting from Stepsize to determine a step size
• α: the reflection parameter $α > 0$:
• γ the expansion parameter $γ > 0$:
• ρ: 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

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

Keyword arguments

source

## Simplex

A simplex for the Nelder-Mead algorithm.

Constructors

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

M::AbstractManifold,
p,
B::AbstractBasis=DefaultOrthonormalBasis();
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.

source

Manopt.StopWhenPopulationConcentratedType
StopWhenPopulationConcentrated <: StoppingCriterion

A stopping criterion for NelderMead to indicate to stop when both

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

drops below a certain tolerance tol_f and tol_p, respectively.

Constructor

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

## Technical details

The NelderMead solver requires the following functions of a manifold to be available