On the Convergence of Pattern Search Algorithms

TLDR

The paper introduces an abstract definition of pattern search methods for solving nonlinear unconstrained optimization problems. Using this characterization, the authors establish a global convergence theory that does not require sufficient decrease, enabled by the fact that pattern search iterates lie on a scaled, translated integer lattice. The definition unifies derivative‑free optimization methods and shows that, by relaxing classical step‑acceptance criteria under stronger step‑form conditions, global convergence can still be guaranteed.

Abstract

We introduce an abstract definition of pattern search methods for solving nonlinear unconstrained optimization problems. Our definition unifies an important collection of optimization methods that neither compute nor explicitly approximate derivatives. We exploit our characterization of pattern search methods to establish a global convergence theory that does not enforce a notion of sufficient decrease. Our analysis is possible because the iterates of a pattern search method lie on a scaled, translated integer lattice. This allows us to relax the classical requirements on the acceptance of the step, at the expense of stronger conditions on the form of the step, and still guarantee global convergence.