Pattern search methods or linearly constrained minimization

We extend pattern search methods to linearly constrained minimization. We d evelop a general class of feasible point pattern search algorithms and prov e global convergence to a Karush-Kuhn-Tucker point. As in the case of uncon strained minimization, pattern search methods for linearly constrained prob lems accomplish this without explicit recourse to the gradient or the direc tional derivative of the objective. Key to the analysis of the algorithms i s the way in which the local search patterns conform to the geometry of the boundary of the feasible region.