Nelder-Mead simplex method

From Glossary

Jump to: navigation, search

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.


Views
Personal tools