This paper introduces the Mesh Adaptive Direct Search (MADS) class of algorithms for nonlinear optimization. MADS extends the Generalized Pattern Search (GPS) class by allowing local exploration, called polling, in an asymptotically dense set of directions in the space of optimization variables. This means that under certain hypotheses, including a weak constraint qualification due to Rockafellar, MADS can treat constraints by the extreme barrier approach of setting the objective to infinity for infeasible points and treating the problem as unconstrained.

The main GPS convergence result is to identify limit points ^x, where the Clarke generalized derivatives are nonnegative in a finite set of directions, called refining directions. Although in the unconstrained case, nonnegative combinations of these directions span the whole space, the fact that there can only be finitely many GPS refining directions limits rigorous justification of the barrier approach to finitely many linear constraints for GPS. The main result of this paper is that the MADS algorithms can generate an asymptotically dense set of refining directions.

For LTMADS, an implementable instance of MADS, the refining directions are dense in the hypertangent cone at ^x with probability 1. This result holds if the iterates associated with the refining directions converge to a single ^x. We compare LTMADS to versions of GPS on some test problems. We also illustrate the limitation of our results with examples.