# Nelder-Mead simplex method

This is a heuristic search (not guaranteed to find a solution) for unconstrained optimization. Let $LaTeX: \textstyle \left \{x^0, x^1, \dots, x^n \right \}$ be $LaTeX: n+1$ points in $LaTeX: \mathbb{R}^n$ that define a simplex. Define the extreme values: $LaTeX: \textstyle f(x^u) = \max \left \{f(x^0), \dots, f(x^n) \right \}$ and $LaTeX: \textstyle f(x^l) = \min \left \{f(x^0), \dots, f(x^n) \right \}.$ Seeking a maximum of $LaTeX: \textstyle f \in \mathbb{R}^n,$ the idea is to replace $LaTeX: x^l$ with a point having a better objective value.

Here is an iteration:
1. Define the centroid of the simplex without this point of least value: $LaTeX: \textstyle c = \sum_i \left \{x^i: i \ne l \right \}/n.$
2. reflection: compute $LaTeX: \textstyle r = c + a(c - x^l),$ where $LaTeX: a > 0$ ($LaTeX: a$ is called the "reflection coefficient").
3. expansion: If $LaTeX: \textstyle f(r) > f(x^l)$ (i.e., we have a better point), compute $LaTeX: \textstyle x = c + b(c - x^l),$ where $LaTeX: b > 1$ ($LaTeX: b$ is called the "expansion coefficient"). If $LaTeX: \textstyle f(x) > f(r), x$ replaces $LaTeX: x^l,$ and the iteration is complete. Otherwise, $LaTeX: r$ replaces $LaTeX: x^l,$ and the iteration is complete.
4. At this step, the reflection point $LaTeX: (r)$ is not better than the worst of the simplex vertices (i.e., $LaTeX: \textstyle f(r) \le f(x^l)$). This is divided into the following cases.
1. If $LaTeX: \textstyle \min \left \{f(x^i): i \ne l \right \} \le f(r) \le f(x^u),$ replace $LaTeX: x^l$ with $LaTeX: r.$
2. If $LaTeX: \textstyle \min \left \{f(x^i): i \ne l \right \} > f(r),$ define $LaTeX: x^*$ as the better of the two: $LaTeX: \textstyle f(x^*) = \max \left \{f(x^l), f(r) \right \}$ (with $LaTeX: \textstyle x^* = x^l \mbox{ or } r,$ resp.). Then, take a contraction step: $LaTeX: \textstyle x = c + d(x^* - c),$ where $LaTeX: 0 < d < 1$ ($LaTeX: d$ is called the "contraction coefficient"). If $LaTeX: \textstyle f(x) > f(x^*), x$ replaces $LaTeX: x^l,$ and the iteration is complete. Otherwise, the last resort is to replace all $LaTeX: x^i$ with: $LaTeX: \textstyle x'^i = (x^i + x^u)/2.$