Pattern search algorithms for bound constrained minimization

We present a convergence theory for pattern search methods for solving boun d constrained nonlinear programs. The analysis relies on the abstract struc ture of pattern search methods and an understanding of how the pattern inte racts with the bound constraints. This analysis makes it possible to develo p pattern search methods for bound constrained problems while only slightly restricting the flexibility present in pattern search methods for unconstr ained problems. We prove global convergence despite the fact that pattern s earch methods do not have explicit information concerning the gradient and its projection onto the feasible region and consequently are unable to enfo rce explicitly a notion of sufficient feasible decrease.