Derivative-Free Optimization: Nelder-Mead and Model-Based Trust-Region Methods

Intuition Beginner

Sometimes you want to minimise a function but you cannot ask it for its slope. Maybe the function is the output of a long simulation, or a physical experiment, or a piece of legacy code nobody can differentiate by hand. You hand it a set of input numbers and it hands you back a single value, and that is all you get. The slope, which gradient methods lean on completely, is simply not on the menu.

You could try to estimate the slope by nudging each input a little and seeing how the output changes. That works when the function is smooth and clean. But if the output is noisy — the simulation has random jitter, the measurement has error — those tiny nudges get swamped by the noise, and your estimated slope points in a random direction. So the honest situation is: no reliable slope, only function values, sometimes noisy and often expensive to get.

Derivative-free optimisation is the family of methods built for exactly this. The idea is to learn about the landscape only from the values you can sample, and to spend those samples wisely because each one costs you. Two broad strategies appear. One keeps a small cluster of sample points and crawls it downhill by replacing its worst member, like an amoeba feeling its way along the floor of a valley. The other fits a smooth approximate bowl through the sample points and minimises the bowl instead, trusting it only nearby — the same caution you would use with any guess built from limited data.

Visual Beginner

Picture three points marking a triangle on a hilly floor, one at each corner. You measure the height at all three. The highest corner is the one you most want to get rid of, so you flip it across the line joining the other two — reflecting it to the opposite side, where the ground is likely lower. If the new spot is great, you push a little further in that direction; if it is still bad, you pull the corner partway back instead. If nothing helps, you shrink the whole triangle toward its best corner and try again. Over many such moves the triangle tumbles and contracts its way toward a low point.

move	when it is used	what it does to the simplex
reflect	first try each step	flips the worst vertex across the others
expand	reflection found the new best	stretches further in that direction
contract	reflection did not help	pulls the worst vertex partway in
shrink	even contraction failed	shrinks everything toward the best vertex

The takeaway: with no slope to follow, a handful of sampled heights and a few simple geometric moves still let you walk downhill — slowly, and with no promise of reaching the true bottom, but using only the values you can actually get.

Worked example Beginner

Take the bowl $f(x_1,x_2)=x_1^2+2x_2^2$ and one reflection step of the simplex method. Start with the triangle whose corners are

$$a=(1,0),b=(0,1),c=(1,1).$$

Measure the heights: $f(a)=1$, $f(b)=2$, $f(c)=1+2=3$. The best corner is $a$ (height $1$), the middle is $b$ (height $2$), and the worst is $c$ (height $3$). We will try to replace the worst corner $c$.

First find the centroid of the other two corners, $a$ and $b$:

$$\bar{x}=\frac{1}{2}(a+b)=\frac{1}{2}((1,0)+(0,1))=(0.5,0.5).$$

Now reflect the worst corner $c$ through this centroid. The reflected point is $r=\bar{x}+(\bar{x}-c)$, that is one full step from $c$ to the far side of the centroid:

$$r=2\bar{x}-c=2(0.5,0.5)-(1,1)=(1,1)-(1,1)=(0,0).$$

Measure its height: $f(r)=0^2+2\cdot 0^2=0$.

Compare. The reflected height $0$ is lower than the current best $f(a)=1$, so reflection did not merely help — it gave the new best corner. The simplex method's rule says: when the reflection is the new best, try expanding further. But even without expanding, we already replace the worst corner $c$ with $r=(0,0)$, and the new triangle has corners $(1,0)$, $(0,1)$, $(0,0)$.

What this tells us: by flipping the worst corner across the other two and measuring one new height, the triangle moved its worst vertex from height $3$ all the way to height $0$, the exact bottom of this bowl — and we never computed a single slope, only four function values.

Check your understanding Beginner

Formal definition Intermediate+

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be the objective, accessible only through a zeroth-order oracle that returns $f(x)$ (possibly with bounded noise) and never $\nabla f(x)$. Derivative-free optimization (DFO) seeks a (local) minimiser of $f$ using only sampled values. Three families are standard.

Nelder-Mead simplex method. Maintain a non-degenerate simplex of $n+1$ vertices $x^0,\dots ,x^n$, ordered so $f(x^0)\le \cdots \le f(x^n)$. Let $\bar{x}=\frac{1}{n}{\sum }_{i=0}^{n-1}{x}^i$ be the centroid of the $n$ best vertices. With reflection ${\delta }^r$, expansion ${\delta }^e$, and contraction ${\delta }^c$ coefficients (classically $1,2,\frac{1}{2}$) and shrink factor $\gamma \in (0,1)$, one iteration computes the reflected point $x^r=\bar{x}+{\delta }^r(\bar{x}-x^n)$ and, by comparing $f(x^r)$ to the ordered vertex values, either accepts $x^r$, computes an expanded point $x^e=\bar{x}+{\delta }^e(\bar{x}-x^n)$, computes a contracted point $x^c=\bar{x}\pm {\delta }^c(\bar{x}-x^n)$, or shrinks every vertex toward $x^0$ via $x^i\leftarrow x^0+\gamma (x^i-x^0)$. The method is a heuristic: no general convergence guarantee holds, and the McKinnon example exhibits a strictly convex $f$ on which it converges to a nonstationary point.

Directional direct search (GPS / MADS). A finite set $D=\{d_1,\dots ,d_m\}\subset {\mathbb{R}}^n$ is a positive spanning set if every $v\in {\mathbb{R}}^n$ is a nonnegative combination $v={\sum }_j{\lambda }_j{d}_j$ with ${\lambda }_j\ge 0$; equivalently the $d_j$ positively span ${\mathbb{R}}^n$. Generalized pattern search (GPS) keeps a current iterate $x_k$ and a mesh of size parameter ${\Delta }_k>0$; a poll step evaluates $f(x_k+{\Delta }_{k}d)$ for $d\in D_k$ (a positive spanning set scaled to the mesh) and accepts any $d$ giving (simple or sufficient) decrease, otherwise shrinks ${\Delta }_k$. Mesh-adaptive direct search (MADS) lets the set of poll directions become asymptotically dense in the unit sphere.

Model-based trust-region DFO. On a sample set $Y=\{y^0,\dots ,y^p\}\subset {\mathbb{R}}^n$ build an interpolation (or regression) model $m_k(x)=c+g^{\top }(x-x_k)+\frac{1}{2}(x-x_k{)}^{\top }H(x-x_k)$ by requiring $m_k(y^i)=f(y^i)$. In a polynomial basis $\varphi =({\varphi }_1,\dots ,{\varphi }_q)$ the coefficients solve $M(\varphi ,Y)\alpha =f(Y)$ with sample matrix $M(\varphi ,Y{)}_{ij}={\varphi }_j(y^i)$. The set $Y$ is poised when $M$ is nonsingular, and $\Lambda$-poised on a region $B$ when the Lagrange polynomials ${\ell }_i$ (defined by ${\ell }_i(y^j)={\delta }_{ij}$) satisfy ${\max }_i{\max }_{x\in B}|{\ell }_i(x)|\le \Lambda$. The model is then minimised over a trust region $\Vert x-x_k\Vert \le {\Delta }_k$ as in 44.03.02. The symbols $D$ (poll set), $\Delta$ (mesh / trust radius), $M(\varphi ,Y)$ (sample matrix), ${\ell }_i$ (Lagrange polynomial), $\Lambda$ (poisedness constant), $f^{\circ }$ (Clarke derivative), and $m$ (model) are recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

• "Nelder-Mead is a convergent optimisation algorithm." It is a heuristic. On the strictly convex McKinnon family the standard Nelder-Mead simplex collapses into a degenerate shape and converges to a point with nonzero gradient. It is robust and popular but carries no general guarantee; the convergence theory of DFO lives with the direct-search and model-based methods, not Nelder-Mead.

• "Any $n$ directions that span ${\mathbb{R}}^n$ suffice for a poll." Spanning is not enough: a basis $\{e_1,\dots ,e_n\}$ spans but does not positively span, so polling only $+e_i$ can miss every descent direction. A positive spanning set needs at least $n+1$ directions (e.g. $\{e_1,\dots ,e_n,-{\sum }_i{e}_i\}$) or the $2n$ coordinate set $\{\pm e_i\}$, guaranteeing some poll direction is descent at any nonstationary point.

• "More sample points always give a better model." Accuracy is governed by the geometry of the sample set, not its size. A sample set with points nearly collinear is ill-poised: $M(\varphi ,Y)$ is near-singular, $\Lambda$ is huge, and the model gradient can be arbitrarily wrong even with many points. Controlling $\Lambda$-poisedness, via geometry-improvement steps, is what makes the model trustworthy.

• "Finite differences are just a slower gradient method." Under noise they can fail outright: a difference quotient $(f(x+h{e}_i)-f(x))/h$ with noise of size $\epsilon$ has error $O(h)+O(\epsilon /h)$, minimised at $h\sim \sqrt{\epsilon }$ with irreducible error $O(\sqrt{\epsilon })$. Implicit filtering exploits this by shrinking $h$ only as the iterates settle, treating the noise floor explicitly rather than pretending the gradient is exact.

Key theorem with proof Intermediate+

The signature result underpinning model-based DFO is the fully-linear error bound: a model built on a $\Lambda$-poised sample set approximates $f$ and its gradient to an accuracy that scales with the trust radius, with a constant controlled by $\Lambda$ alone. This is the inequality that replaces the exact gradient in the convergence theory: wherever a gradient method uses $\nabla f(x_k)$, model-based DFO uses $\nabla m_k(x_k)$ and pays an error proportional to ${\Delta }_k$.

Theorem (fully-linear model from a $\Lambda$-poised set). Let $f$ be continuously differentiable with $L$-Lipschitz gradient on an open set containing the ball $B=B(x_k,\Delta )$, and let $Y=\{y^0,\dots ,y^n\}\subset B$ be $\Lambda$-poised for linear interpolation on $B$. Let $m(x)=c+g^{\top }(x-x_k)$ be the linear interpolation model, $m(y^i)=f(y^i)$. Then there are constants ${\kappa }_f,{\kappa }_g$ depending only on $n$, $L$, and $\Lambda$ such that for all $x\in B$,

$$\Vert \nabla f(x)-g\Vert \le {\kappa }_g\Delta ,|f(x)-m(x)|\le {\kappa }_f{\Delta }^2.$$

Proof. Center coordinates at $x_k$ and write $s^i=y^i-x_k$, so $\Vert s^i\Vert \le \Delta$. Interpolation gives $f(y^i)=c+g^{\top }{s}^i$ for each $i$. Taylor's theorem 02.05.05 with the $L$-Lipschitz gradient gives, for each $i$,

$$f(y^i)=f(x_k)+\nabla f(x_k{)}^{\top }{s}^i+e^i,|e^i|\le \frac{1}{2}L\Vert s^i{\Vert }^2\le \frac{1}{2}L{\Delta }^2.$$

Subtracting the interpolation identity $f(y^i)-f(y^0)=g^{\top }(s^i-s^0)$ from the Taylor identity $f(y^i)-f(y^0)=\nabla f(x_k{)}^{\top }(s^i-s^0)+(e^i-e^0)$ yields, for $i=1,\dots ,n$,

$$(\nabla f(x_k)-g{)}^{\top }(s^i-s^0)=e^0-e^i,|e^0-e^i|\le L{\Delta }^2.$$

Collect these into the matrix $S$ whose rows are $(s^i-s^0{)}^{\top }/\Delta$, so $S(\nabla f(x_k)-g)=b$ with $\Vert b{\Vert }_{\infty }\le L\Delta$. The rows of $S$ have norm $\le 2$, and $\Lambda$-poisedness for linear models is equivalent to a bound $\Vert S^{-1}\Vert \le c_n\Lambda$ on the (scaled) inverse, where $c_n$ depends only on $n$: poisedness is exactly nonsingularity of $S$, and the Lagrange-polynomial bound $\Lambda$ controls the conditioning of $S^{-1}$. Hence

$$\Vert \nabla f(x_k)-g\Vert =\Vert S^{-1}b\Vert \le \Vert S^{-1}\Vert \Vert b\Vert \le c_n\Lambda \cdot \sqrt{n}L\Delta =:{\kappa }_g^{\prime }\Delta .$$

For a general $x\in B$, $\Vert \nabla f(x)-g\Vert \le \Vert \nabla f(x)-\nabla f(x_k)\Vert +\Vert \nabla f(x_k)-g\Vert \le L\Delta +{\kappa }_g^{\prime }\Delta ={\kappa }_g\Delta$. For the value bound, $f(x)-m(x)=[f(x)-f(x_k)-\nabla f(x_k{)}^{\top }(x-x_k)]+[\nabla f(x_k)-g{]}^{\top }(x-x_k)+[f(x_k)-c]$. The first bracket is $O(L{\Delta }^2)$ by Taylor, the second is $\le {\kappa }_g\Delta \cdot \Delta$, and the third is controlled by evaluating the interpolation identity at $y^0$; combining gives $|f(x)-m(x)|\le {\kappa }_f{\Delta }^2$. $\square$

Bridge. This bound is the foundational reason model-based DFO converges without ever seeing a derivative: it certifies that on a geometrically well-placed sample set the model gradient $g$ tracks the true gradient with error $O(\Delta )$, so a step that produces Cauchy decrease for the model 44.03.02 produces real decrease for $f$ up to a controllable error — this is exactly the role the exact gradient plays in line-search theory 44.03.01, with ${\kappa }_g\Delta$ standing in for the (now unavailable) gradient evaluation. The central insight is that geometry replaces differentiation: the single scalar $\Lambda$ that measures how well the sample points are spread plays the part that the Lipschitz constant plays in gradient methods, and the geometry-improvement step that keeps $\Lambda$ bounded is the price paid for working blind. The bound builds toward the global-convergence theorem of the Advanced results, where the criticality step shrinks $\Delta$ precisely so that $\Vert g\Vert \le {\kappa }_g\Delta$ certifies $\Vert \nabla f(x_k)\Vert$ is small, and it appears again in the contrast with positive-spanning direct search, whose convergence instead generalises the gradient through the Clarke derivative rather than through an interpolation model. Putting these together, the two halves of DFO — sampling geometry and nonsmooth calculus — are the two ways to recover stationarity certificates once the gradient is gone; the bridge is that both reduce, in the smooth case, to the same statement that $\nabla f(x_k)\to 0$.

Exercises Intermediate+

Advanced results Master

The fully-linear bound certifies model accuracy; the results below build the convergence theory of derivative-free methods on top of it — the global convergence of the model-based trust-region algorithm, the Clarke-stationarity convergence of mesh-adaptive direct search through nonsmooth calculus, the geometry-management machinery that keeps $\Lambda$ bounded, and the implicit-filtering treatment of noise.

Theorem 1 (global convergence of model-based trust-region DFO). Let $f$ be bounded below and continuously differentiable with $L$-Lipschitz gradient. Run the trust-region algorithm in which, at each iteration, the model $m_k$ is fully linear on $B(x_k,{\Delta }_k)$ with uniform constants ${\kappa }_f,{\kappa }_g$ (enforced by geometry-improvement steps), a criticality step shrinks ${\Delta }_k$ until ${\Delta }_k\le \mu \Vert g_k\Vert$ when $\Vert g_k\Vert$ is small, the step $s_k$ satisfies the fraction-of-Cauchy-decrease condition $m_k(x_k)-m_k(x_k+s_k)\ge c_1\Vert g_k\Vert \min ({\Delta }_k,\Vert g_k\Vert /\Vert H_k\Vert )$ of 44.03.02, and the ratio test accepts or rejects $s_k$ and updates ${\Delta }_k$. Then ${\mathrm{liminf}}_{k\to \infty }\Vert \nabla f(x_k)\Vert =0$, and with the stronger acceptance rule, ${\lim }_{k\to \infty }\Vert \nabla f(x_k)\Vert =0$. The proof mirrors the derivative-based trust-region argument: the Cauchy decrease in the model, transferred to $f$ via the fully-linear bound (an $O({\Delta }_k^2)$ correction to $\mathrm{ared}-\mathrm{pred}$), forces ${\rho }_k\to 1$ for small ${\Delta }_k$ so the radius cannot collapse while $\Vert \nabla f(x_k)\Vert$ stays bounded away from zero, contradicting boundedness below ^{[Conn, A. R., Scheinberg, K. & Vicente, L. N. — Introduction to Derivative-Free Optimization]}.

Theorem 2 (Clarke stationarity of MADS). Let $f$ be Lipschitz near a limit point $x_{\ast }$ of the sequence of mesh-adaptive direct-search iterates, and let the set of normalized poll directions used infinitely often be dense in the unit sphere (the defining property of MADS, which GPS lacks). Then $x_{\ast }$ is Clarke stationary: the generalized directional derivative

$$f^{\circ }(x_{\ast };d)=\underset{y\to x_{\ast },t\downarrow 0}{\mathrm{limsup}}\frac{f(y+td)-f(y)}{t}$$

satisfies $f^{\circ }(x_{\ast };d)\ge 0$ for every direction $d$. When $f$ is strictly differentiable at $x_{\ast }$, this collapses to $\nabla f(x_{\ast })=0$. The mechanism is the failed poll: if $x_k$ is an unsuccessful poll center with mesh size ${\Delta }_k\to 0$ along a refining subsequence, then $f(x_k+{\Delta }_k{d}_k)\ge f(x_k)$ for the poll directions $d_k$, and taking limits along directions converging to any $d$ gives $f^{\circ }(x_{\ast };d)\ge 0$; density of the directions extends this to all $d$. Simple decrease suffices on a rational mesh; for general meshes a sufficient-decrease condition $f(x_k+{\Delta }_{k}d)<f(x_k)-\rho ({\Delta }_k)$ with a forcing function $\rho (t)/t\to 0$ is used ^{[Kolda, T. G., Lewis, R. M. & Torczon, V. — Optimization by Direct Search: New Perspectives on Some Classical and Modern Methods]}.

Theorem 3 (poisedness control and the geometry-improvement step). For any region $B$ and any $\Lambda >1$, there is an algorithm that, given a sample set $Y$, produces in finitely many model evaluations a $\Lambda$-poised set $Y^{\prime }$ on $B$ differing from $Y$ in at most one point per call. The construction works through the Lagrange polynomials: if some ${\max }_{x\in B}|{\ell }_i(x)|>\Lambda$, replace $y^i$ by a maximizer $x^{\ast }=\arg {\max }_{x\in B}|{\ell }_i(x)|$, which strictly increases $|\det M(\varphi ,Y)|$ by the factor $|{\ell }_i(x^{\ast })|>\Lambda$; iterating drives the Lagrange polynomials below $\Lambda$. The bound $\Lambda$ then controls the fully-linear constants ${\kappa }_f,{\kappa }_g$ of the Key theorem, so a uniform bound on $\Lambda$ across iterations is exactly the uniform model accuracy that Theorem 1 requires. This decouples the optimization progress (the trust-region step) from the geometry maintenance (the poisedness step), the two being interleaved by the criticality test ^{[Conn, A. R., Scheinberg, K. & Vicente, L. N. — Introduction to Derivative-Free Optimization]}.

Theorem 4 (implicit filtering for noisy objectives). Suppose the oracle returns $\tilde{f}=f+\eta$ with $\Vert \eta {\Vert }_{\infty }\le \epsilon$ on the region of interest and $f$ smooth. Implicit filtering computes a forward-difference (or central-difference) gradient ${\nabla }_h\tilde{f}$ with stencil width $h$ and takes a (projected) quasi-Newton step, reducing $h$ only when the line search along $-{\nabla }_h\tilde{f}$ fails or the difference gradient falls below a multiple of $h$. By Exercise 6 the difference gradient has error $O(Lh)+O(\epsilon /h)$, so for $h$ above the noise scale $\sqrt{\epsilon /L}$ it is a usable descent direction; shrinking $h$ as the iterates settle tracks the descending noise floor. The method converges to a point where $\Vert \nabla f\Vert =O(\sqrt{\epsilon })$, the irreducible accuracy set by the noise — the honest ceiling for a finite-difference method on a noisy objective, and the reason model-based and direct-search methods, which never differentiate, are preferred when $\epsilon$ is large relative to the curvature scale ^{[Nocedal, J. & Wright, S. J. — Numerical Optimization (2nd ed.)]}.

Synthesis. Derivative-free optimization is one problem — minimise $f$ from values alone — answered by three strategies, and the foundational reason the rigorous ones converge is that each manufactures a stationarity certificate to replace the missing gradient. The central insight is that there are two such certificates: the model-based methods build a fully-linear model whose gradient tracks $\nabla f$ with error ${\kappa }_g\Delta$, so the trust-region machinery of 44.03.02 transfers verbatim once $\Lambda$-poisedness is maintained; the direct-search methods instead poll a positive spanning set, and a failed poll on a refining mesh is a certificate of Clarke stationarity, the nonsmooth generalisation of $\nabla f=0$. This is exactly the duality between geometry and nonsmooth calculus: a bounded poisedness constant $\Lambda$ is dual to a dense set of refining poll directions, and both reduce, in the smooth case, to $\nabla f(x_k)\to 0$.

The criticality step is the bridge inside the model-based method — it refines $\Delta$ until a small model gradient provably implies a small true gradient, generalising the radius management of 44.03.02 to the case where the gradient is itself estimated. Nelder-Mead sits outside this theory as a robust heuristic with no guarantee, and implicit filtering occupies the noisy middle ground where finite differences survive only down to the $O(\sqrt{\epsilon })$ floor. Putting these together, the chapter's gradient-based globalisation — the Wolfe line search of 44.03.01 and the Cauchy-decrease trust region of 44.03.02 — is recovered without derivatives, the price being model evaluations spent on geometry rather than on differentiation, and the convergence theorem appears again wherever an optimisation method must certify stationarity from incomplete first-order information.

Full proof set Master

Proposition 1 (positive spanning sets contain a descent direction). If $D$ positively spans ${\mathbb{R}}^n$ and $v\ne 0$, then $v^{\top }d>0$ for some $d\in D$. Consequently if $\nabla f(x)\ne 0$, some $d\in D$ is a descent direction at $x$.

Proof. Write $v={\sum }_{d\in D}{\lambda }_{d}d$ with ${\lambda }_d\ge 0$, possible by positive spanning. Then $0<\Vert v{\Vert }^2=v^{\top }v={\sum }_d{\lambda }_d(v^{\top }d)$. If every $v^{\top }d\le 0$ the sum would be $\le 0$, contradicting positivity; so $v^{\top }d>0$ for some $d$. Taking $v=-\nabla f(x)$ gives $-\nabla f(x{)}^{\top }d>0$, a descent direction. $\square$

Proposition 2 (fully-linear error bound, $\Lambda$-poised linear model). Under the hypotheses of the Key theorem there are ${\kappa }_f,{\kappa }_g$ depending only on $n,L,\Lambda$ with $\Vert \nabla f(x)-g\Vert \le {\kappa }_g\Delta$ and $|f(x)-m(x)|\le {\kappa }_f{\Delta }^2$ on $B(x_k,\Delta )$.

Proof. As in the Key theorem. Centering at $x_k$, the interpolation and Taylor identities give $S(\nabla f(x_k)-g)=b$ with rows of $S$ equal to $(y^i-y^0{)}^{\top }/\Delta$ and $\Vert b{\Vert }_{\infty }\le L\Delta$. $\Lambda$-poisedness bounds $\Vert S^{-1}\Vert \le c_n\Lambda$, so $\Vert \nabla f(x_k)-g\Vert \le c_n\Lambda \sqrt{n}L\Delta$; extending to $x\in B$ by the $L$-Lipschitz gradient gives the gradient bound with ${\kappa }_g=(1+c_n\Lambda \sqrt{n})L$. The value bound follows by writing $f(x)-m(x)$ as the Taylor remainder plus the gradient-error term plus the constant-fit error, each $O({\Delta }^2)$. $\square$

Proposition 3 (criticality certificate). If $m_k$ is fully linear on $B(x_k,{\Delta }_k)$ with constant ${\kappa }_g$ and the criticality step enforces ${\Delta }_k\le \mu \Vert g_k\Vert$, then $\Vert g_k\Vert \ge \Vert \nabla f(x_k)\Vert /(1+{\kappa }_g\mu )$.

Proof. From Proposition 2 at $x=x_k$, $\Vert \nabla f(x_k)-g_k\Vert \le {\kappa }_g{\Delta }_k\le {\kappa }_g\mu \Vert g_k\Vert$. The triangle inequality gives $\Vert \nabla f(x_k)\Vert \le \Vert g_k\Vert +{\kappa }_g\mu \Vert g_k\Vert =(1+{\kappa }_g\mu )\Vert g_k\Vert$, and rearranging yields the claim. $\square$

Proposition 4 ($\mathrm{liminf}$ global convergence of model-based DFO). Let $f$ be bounded below and $C^1$ with $L$-Lipschitz gradient, the models uniformly fully linear, the steps satisfying the fraction-of-Cauchy-decrease condition with constant $c_1$, and $\Vert H_k\Vert \le \beta$. Then ${\mathrm{liminf}}_k\Vert \nabla f(x_k)\Vert =0$.

Proof sketch (full argument in Conn-Scheinberg-Vicente Ch. 10). Suppose $\Vert \nabla f(x_k)\Vert \ge ϵ>0$ for all large $k$. By Proposition 3 the criticality step keeps $\Vert g_k\Vert \ge ϵ/(1+{\kappa }_g\mu )=:{ϵ}^{\prime }>0$, so the predicted reduction is ${\mathrm{pred}}_k=m_k(x_k)-m_k(x_k+s_k)\ge c_1{ϵ}^{\prime }\min ({\Delta }_k,{ϵ}^{\prime }/\beta )$. The fully-linear value bound gives $|{\mathrm{ared}}_k-{\mathrm{pred}}_k|\le |f(x_k)-m_k(x_k)|+|f(x_k+s_k)-m_k(x_k+s_k)|\le 2{\kappa }_f{\Delta }_k^2$. Hence $|{\rho }_k-1|\le 2{\kappa }_f{\Delta }_k^2/{\mathrm{pred}}_k\to 0$ as ${\Delta }_k\to 0$, so there is $\bar{\Delta }$ with ${\rho }_k>\frac{1}{4}$ whenever ${\Delta }_k\le \bar{\Delta }$; the radius-update rule then keeps ${\Delta }_k\ge \delta >0$ for all large $k$. Each accepted step reduces $f$ by at least ${\eta }^{\prime }{\mathrm{pred}}_k\ge \frac{1}{2}{c}_1{ϵ}^{\prime }\min (\delta ,{ϵ}^{\prime }/\beta )>0$, and infinitely many such reductions drive $f\to -\infty$, contradicting boundedness below. Therefore ${\mathrm{liminf}}_k\Vert \nabla f(x_k)\Vert =0$. $\square$

Proposition 5 (geometry improvement increases the determinant). Let $Y$ be poised on $B$ with Lagrange polynomials ${\ell }_i$, and suppose ${\max }_{x\in B}|{\ell }_k(x)|={\Lambda }_k>\Lambda$ at some index $k$. Replacing $y^k$ by $x^{\ast }=\arg {\max }_{x\in B}|{\ell }_k(x)|$ yields $Y^{\prime }$ with $|\det M(\varphi ,Y^{\prime })|={\Lambda }_k|\det M(\varphi ,Y)|>\Lambda |\det M(\varphi ,Y)|$.

Proof. The Lagrange polynomials satisfy ${\ell }_i(y^j)={\delta }_{ij}$, so by Cramer's rule the ratio of determinants when $y^k$ is replaced by any point $x$ is $\det M(\varphi ,Y\cup \{x\}\setminus \{y^k\})/\det M(\varphi ,Y)={\ell }_k(x)$ (expanding the determinant along the changed row, the cofactor structure gives exactly the $k$-th Lagrange polynomial evaluated at the new point). Choosing $x=x^{\ast }=\arg {\max }_{x\in B}|{\ell }_k(x)|$ multiplies $|\det M|$ by $|{\ell }_k(x^{\ast })|={\Lambda }_k>\Lambda$. Iterating over indices with oversized Lagrange polynomials monotonically increases $|\det M|$, which is bounded above on the compact $B$, so the process terminates with all $|{\ell }_i|\le \Lambda$, i.e. a $\Lambda$-poised set. $\square$

Connections Master

• Line-search methods and the Wolfe conditions 44.03.01 are the derivative-based template that derivative-free optimization reconstructs without a gradient: the sufficient-decrease and curvature conditions that globalise a descent direction there reappear as the simple-decrease and sufficient-decrease conditions of direct search, and the angle-condition guarantee — that the search direction stays bounded away from orthogonality to $-\nabla f$ — is precisely what a positive spanning set enforces structurally, since one of its members is always a descent direction (Proposition 1). The Zoutendijk summability that powers line-search convergence is replaced, in the smooth case, by the failed-poll certificate of Clarke stationarity.

• Trust-region methods, the Cauchy point, and the dogleg step 44.03.02 are the engine the model-based branch runs on directly: the derivative-free trust-region algorithm is the trust-region algorithm of that unit with the exact Taylor model replaced by an interpolation model on a $\Lambda$-poised sample set, and the Cauchy sufficient-reduction bound and ratio test carry over verbatim. What is new is the criticality step and the geometry-improvement step, which manage the model gradient $g_k=\nabla m_k(x_k)$ in place of the exact gradient; the fully-linear bound $\Vert \nabla f(x_k)-g_k\Vert \le {\kappa }_g{\Delta }_k$ is the single inequality that lets the convergence proof of 44.03.02 proceed unchanged.

• Finite-difference and automatic differentiation 44.03.08 is the contrasting approach this unit sets itself against: where that unit estimates the gradient by differencing (or computes it exactly by AD on differentiable code), derivative-free optimization is the regime where neither is available — AD cannot reach black-box or legacy code, and finite differences fail under noise with the irreducible $O(\sqrt{\epsilon })$ floor of Exercise 6. Implicit filtering is the bridge between the two: it uses finite differences but shrinks the stencil only as the iterates settle, treating the noise floor explicitly rather than assuming the difference gradient is exact.

• Multivariable Taylor expansion and the test for extrema 02.05.05 supplies the analytic core of the fully-linear bound: the model error is the Taylor remainder of $f$ controlled by the Lipschitz constant of its gradient, and the poisedness condition is exactly what makes the linear system relating interpolation data to that remainder invertible with a controlled inverse. The stationarity certificate that derivative-free methods drive toward, $\nabla f(x_{\ast })=0$, is the first-order necessary condition for an extremum established there.

Historical & philosophical context Master

The simplex method for function minimisation — distinct from Dantzig's simplex method for linear programming — was introduced by John Nelder and Roger Mead in 1965, building on an earlier simplex idea of Spendley, Hext, and Himsworth in 1962 ^{[Nelder-Mead 1965]}. Its robustness and the fact that it needs only function values made it one of the most widely used optimisation routines in science and engineering, despite the absence of a convergence proof. Ken McKinnon in 1998 settled the theoretical question by exhibiting a family of strictly convex functions on which the standard Nelder-Mead iteration converges to a nonstationary point, confirming that the method is a heuristic ^{[McKinnon 1998]}.

The convergent theory of derivative-free methods developed along two lines. The pattern-search idea — polling a fixed geometric pattern of directions — goes back to Hooke and Jeeves in 1961 and to coordinate search, and was given a rigorous convergence framework by Virginia Torczon in 1997 under the name generalized pattern search, with the positive-spanning-set structure made central by the survey of Kolda, Lewis, and Torczon in 2003 ^{[Kolda-Lewis-Torczon 2003]}. Charles Audet and John Dennis in 2006 introduced mesh-adaptive direct search (MADS), whose asymptotically dense poll directions yield the Clarke-stationarity guarantee that GPS cannot reach ^{[Audet-Dennis 2006]}. The model-based branch, in which a quadratic is interpolated on a controlled sample set, was driven by M. J. D. Powell through the 1990s and 2000s in his UOBYQA, NEWUOA, and BOBYQA solvers, and the poisedness theory and convergence analysis were systematised by Andrew Conn, Katya Scheinberg, and Luis Vicente in their 2009 monograph ^{[Conn-Scheinberg-Vicente 2009]}, the standard reference for the field.

Bibliography Master

@book{NocedalWright2006dfo,
  author    = {Nocedal, Jorge and Wright, Stephen J.},
  title     = {Numerical Optimization},
  edition   = {2},
  series    = {Springer Series in Operations Research and Financial Engineering},
  publisher = {Springer},
  year      = {2006}
}

@book{ConnScheinbergVicente2009,
  author    = {Conn, Andrew R. and Scheinberg, Katya and Vicente, Luis N.},
  title     = {Introduction to Derivative-Free Optimization},
  series    = {MPS-SIAM Series on Optimization},
  publisher = {SIAM},
  year      = {2009}
}

@article{NelderMead1965,
  author  = {Nelder, John A. and Mead, Roger},
  title   = {A Simplex Method for Function Minimization},
  journal = {The Computer Journal},
  volume  = {7},
  number  = {4},
  year    = {1965},
  pages   = {308--313}
}

@article{McKinnon1998,
  author  = {McKinnon, Ken I. M.},
  title   = {Convergence of the Nelder-Mead Simplex Method to a Nonstationary Point},
  journal = {SIAM Journal on Optimization},
  volume  = {9},
  number  = {1},
  year    = {1998},
  pages   = {148--158}
}

@article{KoldaLewisTorczon2003,
  author  = {Kolda, Tamara G. and Lewis, Robert Michael and Torczon, Virginia},
  title   = {Optimization by Direct Search: New Perspectives on Some Classical and Modern Methods},
  journal = {SIAM Review},
  volume  = {45},
  number  = {3},
  year    = {2003},
  pages   = {385--482}
}

@article{AudetDennis2006,
  author  = {Audet, Charles and Dennis, J. E., Jr.},
  title   = {Mesh Adaptive Direct Search Algorithms for Constrained Optimization},
  journal = {SIAM Journal on Optimization},
  volume  = {17},
  number  = {1},
  year    = {2006},
  pages   = {188--217}
}

@article{Torczon1997,
  author  = {Torczon, Virginia},
  title   = {On the Convergence of Pattern Search Algorithms},
  journal = {SIAM Journal on Optimization},
  volume  = {7},
  number  = {1},
  year    = {1997},
  pages   = {1--25}
}