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.