Analysis of Generalized Pattern Searches

Abstract. This paper contains a new convergence analysis for the Lewis and Torczon GPS class of pattern search methods for linearly constrained optimization. The analysis is motivated by the desire to understand the behavior of the algorithm under hypotheses more consistent with properties satisfied in practice for a class of problems, discussed at various points in the paper, for which these methods are successful. Specifically, even if the objective function is discontinuous or extended valued, the methods find a limit point with some minimizing properties. Simple examples show that the strength of the optimality conditions at a limit point does not depend only on the algorithm, but also on the directions it uses, and on the smoothness of the objective at the limit point in question. This contribution of this paper is to provide a simple convergence analysis that supplies detail about the relation of optimality conditions to objective smoothness properties, and the defining directions for the algorithm, and it gives older results as easy corollaries. Key words. Pattern search algorithm, linearly constrained optimization, surrogate-based opti-mization, nonsmooth optimization, derivative-free convergence analysis. AMS subject classifications. 90C30, 90C56, 65K05