Using Sampling and Simplex Derivatives in Pattern Search Methods

TLDR

The paper proposes enhancing pattern search efficiency by reusing past objective evaluations through simplex derivative computations. It details computing accurate simplex gradients from prior points, then using them to reorder poll evaluations or adjust mesh size without new function calls, and applies these techniques to CUTEr benchmark problems. Numerical experiments demonstrate that these methods substantially improve the practical performance of pattern search algorithms.

Abstract

In this paper, we introduce ways of making a pattern search more efficient by reusing previous evaluations of the objective function, based on the computation of simplex derivatives (e.g., simplex gradients). At each iteration, one can attempt to compute an accurate simplex gradient by identifying a sampling set of previously evaluated points with good geometrical properties. This can be done using only past successful iterates or by considering all past function evaluations. The simplex gradient can then be used to reorder the evaluations of the objective function associated with the directions used in the poll step or to update the mesh size parameter according to a sufficient decrease criterion, neither of which requires new function evaluations. We present these procedures in detail and apply them to a set of problems from the CUTEr collection. Numerical results show that these procedures can enhance significantly the practical performance of pattern search methods.