On the Convergence of Pattern Search Algorithms

. This paper gives a unifying, abstract generalization of pattern search methods for solving nonlinear optimization problems. Pattern search methods are a class of direct search methods--- methods that neither require nor explicitly approximate derivatives. We use the abstract description of pattern search methods to establish a global first-order stationary point convergence theory that neither requires the directional derivative nor enforces a notion of sufficient decrease. We also discuss the relationship between the convergence analysis for pattern search methods and the analysis for both line search and model trust region globalization strategies; in particular, the fact that we can relax the requirements on the acceptance of the step, at the expense of stronger conditions on the form of the step, and still guarantee global convergence. Key words. unconstrained optimization, convergence analysis, direct search methods, model trust region methods, line search methods, globalizatio...