Nelder-Mead simplex method
This is a heuristic search (not guaranteed to find a solution) for unconstrained optimization. Let be points in that define a simplex. Define the extreme values: and Seeking a maximum of the idea is to replace with a point having a better objective value.
- Here is an iteration:
- Define the centroid of the simplex without this point of least value:
- reflection: compute where ( is called the "reflection coefficient").
- expansion: If (i.e., we have a better point), compute where ( is called the "expansion coefficient"). If replaces and the iteration is complete. Otherwise, replaces and the iteration is complete.
- At this step, the reflection point is not better than the worst of the simplex vertices (i.e., ). This is divided into the following cases.
- If replace with
- If define as the better of the two: (with resp.). Then, take a contraction step: where ( is called the "contraction coefficient"). If replaces and the iteration is complete. Otherwise, the last resort is to replace all with: