Finite-budget Nelder–Mead simplex procedure

Finite sums of vectors in ${\mathbb{R}}^n$ use the additive finite-list sum of Linear combination of a finite list, and the span $\mathrm{span}(S)$ as the smallest linear subspace containing $S$; sums of real coefficients use Finite sums and finite products, by recursion.

Fix $n\ge 1$, an objective oracle $f:{\mathbb{R}}^n\to \mathbb{R}\cup \{\text{nonfinite}\}$, a finite integer call budget $B\ge 0$, positive tolerances ${\epsilon }_x,{\epsilon }_f$, and an ordered initial simplex $(v_0,\dots ,v_n)$. Call the ordered tuple nondegenerate when, for real coefficients ${\lambda }_1,\dots ,{\lambda }_n$, ${\sum }_{i=1}^n{\lambda }_i(v_i-v_0)=0$ implies every ${\lambda }_i=0$. Use reflection $\alpha =1$, expansion $\gamma =2$, contraction $\rho =1\mathrm{/}2$, and shrink $\sigma =1\mathrm{/}2$. Ties in sorting objective values are broken by current vertex slot, lower slot first. When recording the best point seen, replace it only on a strict objective improvement, so ties retain the earliest evaluation; initial vertices are evaluated in slot order.

If the initial simplex is degenerate, return degenerate-simplex. If $B<n+1$, return budget-exhausted with zero calls and no best point. Otherwise evaluate initial vertices in slot order, counting every call. A nonfinite result returns nonfinite-objective and the best finite point seen, if any. For each committed simplex, let $x_b$ be its sorted best vertex, $x_w$ its worst, let $x_2$ denote the second-worst (the best when $n=1$), and set $c:=n^{-1}{\sum }_{i=0}^{n-1}{x}_i$ using the sorted vertices $x_0,\dots ,x_n$. Define the diameter $D={\max }_{0\le i,j\le n}\mathrm{\parallel }{x}_i-x_j{\mathrm{\parallel }}_2$, and spread $S=f(x_w)-f(x_b)$. Stop with tolerance-met exactly when both $D\le {\epsilon }_x$ and $S\le {\epsilon }_f$.

Otherwise evaluate reflection $x_r=c+(c-x_w)$. If $f(x_r)<f(x_b)$, evaluate expansion $x_e=c+2(x_r-c)$ and replace $x_w$ by $x_e$ iff $f(x_e)<f(x_r)$; a tie keeps reflection. If $f(x_b)\le f(x_r)<f(x_2)$, where $x_2$ is the second-worst vertex, replace $x_w$ by reflection. If $f(x_2)\le f(x_r)<f(x_w)$, evaluate outside contraction $x_{oc}=c+(x_r-c)\mathrm{/}2$ and accept iff $f(x_{oc})\le f(x_r)$; equality accepts. If $f(x_r)\ge f(x_w)$, evaluate inside contraction $x_{ic}=c+(x_w-c)\mathrm{/}2$ and accept iff $f(x_{ic})<f(x_w)$; equality fails. A failed contraction proposes $s_i=x_b+(x_i-x_b)\mathrm{/}2$ for each sorted nonbest vertex $x_i$, $1\le i\le n$, retaining $x_b$. Evaluate $f(s_i)$ in increasing $i$, making a new call even if $s_i$ was evaluated earlier. Apply the budget and nonfinite-result rules below to every such call. Commit the shrunk simplex, in these sorted slots, only after all $n$ values are finite and the complete update passes the nondegeneracy check.

Count every objective call, including rejected trials. Before a needed call, if the budget is exhausted, return budget-exhausted with the last committed simplex and best finite point seen; do not partially commit an update. A nonfinite trial returns nonfinite-objective with the same committed simplex. If a proposed complete update is degenerate, return degenerate-simplex without committing it. After a valid update, recheck both tolerances. No general convergence guarantee is asserted.