Nelder Mead method

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

Solve a Nelder-Mead minimization problem for the cost function $f: \mathcal M$ on the manifold M. If the initial population p is not given, a random set of points is chosen.

This algorithm is adapted from the Euclidean Nelder-Mead method, see https://en.wikipedia.org/wiki/Nelder-Mead_method and http://www.optimization-online.org/DB_FILE/2007/08/1742.pdf.

Input

• M: a manifold $\mathcal M$
• f: a cost function to minimize
• population: ($n+1$rand(M)s) an initial population of $n+1$ points, where $n$ is the dimension of the manifold M.

Optional

• stopping_criterion: (StopAfterIteration(2000) |StopWhenPopulationConcentrated()) a StoppingCriterion
• α: (1.) reflection parameter ($α > 0$)
• γ: (2.) expansion parameter ($γ$)
• ρ: (1/2) contraction parameter, $0 < ρ ≤ \frac{1}{2}$,
• σ: (1/2) shrink coefficient, $0 < σ ≤ 1$
• retraction_method: (default_retraction_method(M, typeof(p))) the retraction to use
• inverse_retraction_method: (default_inverse_retraction_method(M, typeof(p))) an inverse retraction to use.

and the ones that are passed to decorate_state! for decorators.

Output

the obtained (approximate) minimizer $p^*$, see get_solver_return for details

NelderMead(M::AbstractManifold, f [, population::NelderMeadSimplex])

Solve a Nelder Mead minimization problem for the cost function f on the manifold M. If the initial population population is not given, a random set of points is chosen. If it is given, the computation is done in place of population.

For more options see NelderMead.

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

• population an Array{point,1} of $n+1$ points $x_i$, $i=1,…,n+1$, where $n$ is the dimension of the manifold.
• stopping_criterion: (StopAfterIteration(2000) |StopWhenPopulationConcentrated()) a StoppingCriterion
• α: (1.) reflection parameter ($α > 0$)
• γ: (2.) expansion parameter ($γ > 0$)
• ρ: (1/2) contraction parameter, $0 < ρ ≤ \frac{1}{2}$,
• σ: (1/2) shrink coefficient, $0 < σ ≤ 1$
• p: (copy(population.pts[1])) - a field to collect the current best value (initialized to some point here)
• retraction_method: (default_retraction_method(M, typeof(p))) the retraction to use.
• inverse_retraction_method: (default_inverse_retraction_method(M, typeof(p))) an inverse retraction to use.

Constructors

NelderMeadState(M[, population::NelderMeadSimplex]; kwargs...)

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

In the constructor all fields (besides the population) are keyword arguments.

NelderMeadSimplex

A simplex for the Nelder-Mead algorithm.

Constructors

NelderMeadSimplex(M::AbstractManifold)

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

NelderMeadSimplex(
    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.

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)