Derivative-free models and direct search

A linear interpolation model in n variables has n+1 coefficients; a full quadratic has (n+1)(n+2)/2. At least that many appropriately positioned value samples are required for unique interpolation of the chosen class. The geometry matters as much as the count: nearly coincident or poorly arranged points can make fitted coefficients extremely sensitive to small value errors. Model-based trust-region methods maintain useful interpolation geometry while limiting the radius over which the fit is trusted.

Fully linear is a quantitative model-quality concept: within a ball of radius Δ, objective error is bounded by a constant times Δ squared and gradient error by a constant times Δ. Those bounds depend on smoothness and controlled sample geometry; they are not guaranteed by calling a polynomial an interpolant. A model can be optimized cheaply, but a trial still needs a new objective evaluation to compare predicted and actual reduction. The expensive resource is often that sequence of simulator calls, not the arithmetic used to solve the fitted model.

Direct search can poll points along a finite positive-spanning set of directions, such as both signs of every coordinate vector. Positive spanning ensures that a nonzero negative gradient has a useful projection onto at least one poll direction. Accept a point only if its decrease exceeds a forcing amount, for example c times the squared poll radius. If every direction fails this sufficient-decrease test, the failed poll contains information about the possible gradient size.

For unit coordinate directions and an L-Lipschitz gradient, select the sign opposite each gradient component. Combining its failed decrease with the smoothness upper bound yields an absolute component bound of (c+L/2) times the radius. Summing coordinate squares gives a Euclidean norm bound with a square-root dimension factor. This is a mathematical consequence under known smoothness and exact values. An implementation without a valid L cannot print that numerical certificate merely because it observed an unsuccessful poll.

If objective evaluations contain absolute errors of size delta, decreasing the sample spacing does not indefinitely improve a derivative estimate. Differences divide those errors by the spacing. Likewise, a direct-search forcing decrease smaller than the evaluation uncertainty cannot be reliably distinguished from noise. Repetition, common random numbers, statistical acceptance rules, or a noise-aware stopping radius may be necessary. Those modifications require their own analysis instead of borrowing an exact deterministic guarantee.

For smooth, lower-bounded deterministic objectives, suitable positive-spanning polls, sufficient-decrease rules, controlled radius updates, and bounded direction geometry support stationarity and evaluation-complexity results. Their constants include dimension and directional coverage. They do not imply that every popular heuristic, including every variant of simplex search, has the same guarantee. Always specify which function calls count, whether parallel polls change elapsed time rather than total work, and whether the available budget can support the chosen local model dimension.