Recipe

Run one Nelder-Mead iteration

Use when: you have three (or, in general, n+1) trial points and only function VALUES to compare, no derivative available at all

Goal: a new simplex, no worse than the old one, that has crept toward the minimum

Taught in Pattern search and Nelder-Mead

1. 1

   Evaluate f at every vertex; label the best, second, and worst. Compute c= the average of every vertex EXCEPT the worst.

   Example

   For f(x,y)=(x-2)^2+2(y-3)^2 on triangle (0,0),(2,0),(0,2): values 22,18,6, so best =(0,2), second =(2,0), worst =(0,0), and c=(1,1).

   Why: only the worst vertex ever moves in one iteration -- the centroid of the other two is what it reflects through.

2. 2

   Compute x_r=c+(c-x_{\text{worst}}) and evaluate f(x_r).

   Example

   x_r=(1,1)+((1,1)-(0,0))=(2,2), f(x_r)=(2-2)^2+2(2-3)^2=2.

   Why: reflecting through the centroid tries the mirror-image side of the triangle from the worst point -- the most likely direction to improve.

3. 3

   Compare f(x_r) against the best, second, and worst vertices' own values to pick exactly one of four moves.

   Example

   f(x_r)=2<f_{\text{best}}=6, so try expansion: x_e=(1,1)+2((1,1)-(0,0)) =(3,3), f(x_e)=1<f(x_r)=2 — expansion wins.

   • f(x_r)<f_{\text{best}} — try expansion x_e=c+2(c-x_{\text{worst}}); keep whichever of x_e,x_r is better.
   • f_{\text{best}}\le f(x_r)<f_{\text{second}} — accept x_r outright, replacing the worst vertex.
   • f_{\text{second}}\le f(x_r)<f_{\text{worst}} — try an OUTSIDE contraction x_c=c+0.5(c-x_{\text{worst}}); accept it if it beats x_r, else shrink.
   • f(x_r)\ge f_{\text{worst}} — try an INSIDE contraction x_c=c-0.5(c-x_{\text{worst}}); accept it if it beats the worst, else shrink.

   Why: reflection alone found a real improvement; expansion checks whether pushing further in the SAME direction pays off even more, cheaply, before committing.

4. 4

   The winning point from Step 3 replaces x_{\text{worst}}; the other two vertices are unchanged. Return to Step 1 on the new triangle.

   ⚡ Shortcut

   If Step 3 lands in the shrink case, skip straight to replacing EVERY vertex except the best: x_i\leftarrow x_{\text{best}}+0.5(x_i-x_{\text{best}}) for both other vertices, instead of a single-vertex replacement.

   Why: only the worst vertex was ever a candidate for replacement in the reflect/expand/contract branches -- the best and second-best already earned their place this round.