Nelder-Mead method

There are occasions where it has been spectacularly good ... Mathematicians hate it because you can’t prove convergence; engineers seem to love it because it often works. -- John Nelder

The Nelder-Mead (NM) method (also called downhill simplex method is a heuristic (search method for minimizing an objective function $f({\bf x}$ given in an N-dimensional space. The key concept of the mehtod is the simplex, an $N$ dimensional polytope that is a convex hull of a set of $N+1$ linearly independent points ${\bf x}_0,\cdots,{\bf x}_N$. These points are linearly independent in the sense that the $N$ vectors $\{{\bf x}_0,\cdots,{\bf x}_N\}$ are linearliy independent (no three points are colinear):

$$S=\left\{\sum_{i=0}^Nc_i{\bf x}_i \;\bigg\vert\;\sum_{i=0}^Nc_i=1, \;\;\;\;c_i\ge 0\right\}$$ (21)

Intuitively, a simplex is a volumn in the N-D space enclosed by flat surfaces and spanned by $N+1$ verticies. For example, a simplex is a line sigment spanned by 2 points in 1-D space, a triangle spanned by 3 points in 2-D space, and a tetrahedron spanned by 4 points in 3-D space.

The NM method is an iterative process which transforms an initial simplex iteratively into a different one following a path in the space along which the function values are progressively reduced. The initial simplex can be generated based on a single point ${\bf x}_0$, an initial guess, by adding a constant along each of the $N$ dimensions spanned by the standard basis $\{{\bf e}_1,\cdots,{\bf e}_N\}$:

$${\bf x}_i={\bf x}_0+c{\bf e}_i$$ (22)

In the subsequent iterations, the initial simplex is transformed based on four parameters:

• reflection coefficient: $\alpha>0$, e.g., $\alpha=1$
• expansion coefficient: $0<\beta<1$, e.g., $\beta=1/2$
• contraction coefficient: $\gamma>1$, e.g., $\gamma=2$
• shrink coefficient: $0<\delta<1$, e.g., $\delta=1/2$

Specially here are the steps in each iteration:

• Order all $N+1$ vertex points according to their function values:

  $$f({\bf x}_0)\le f({\bf x}_1)\le\cdots\le f({\bf x}_N)$$ (23)

  Denote the best point with lowest function value by ${\bf x}_0={\bf x}_l$, the worst point with the highest function value by ${\bf x}_N={\bf x}_h$, and the second worst point by ${\bf x}_{N-1}={\bf x}_s$.
• Find the centroid of all points except the worst one ${\bf x}_N={\bf x}_h$:

  $${\bf c}=\frac{1}{N}\sum_{i=1}^N{\bf x}_i$$ (24)

• Find a new reflection point:

  $${\bf x}_r={\bf c}+\alpha({\bf c}-{\bf x}_h)$$ (25)

  Depending on the function value $f({\bf x}_r)$, we will do one of the following:
  • If $f({\bf x}_s<f({\bf x}_r)<f({\bf x}_l)$, then replace ${\bf x}_h$ by ${\bf x}_r$.
  • If $f({\bf x}_r)<f({\bf x}_l)$, get an expansion point

    $${\bf x}_e={\bf c}+\gamma({\bf x}_r-{\bf c})$$ (26)

    Replace ${\bf x}_h$ by the better (with lower function value) of ${\bf x}_r$ and ${\bf x}_e$. This is called greedy optimization.
  • $f({\bf x}_r)>f({\bf x}_s)$, i.e., ${bf x}_r-{\bf c}$ is a wrong direction, get a contraction point

    $${\bf x}_c={\bf c}+\beta({\bf x}_h-{\bf c})$$ (27)

    If $f({\bf x}_c)<f({\bf x}_h)$ is better than ${\bf x}_h$, replace ${\bf x}_h$ by ${\bf x}_c$
  • Terminate the iteration when the variance of the $N+1$ function values at the vertices of the current simplex is smaller than a tolerance. The best point ${\bf x}_0$ with lowest function value is returned as the solution.