Mesh adaptive direct search algorithms for constrained optimization

This paper addresses the problem of minimization of a nonsmooth function undergeneral nonsmooth constraints when no derivatives of the objective or constraint functions are avail-able. We introduce the mesh adaptive direct search (MADS) class of algorithms which extends thegeneralized pattern search (GPS) class by allowing local exploration, called polling, in an asymptot-ically dense set of directions in the space of optimization variables. This means that under certainhypotheses, including a weak constraint qualification due to Rockafellar, MADS can treat constraintsby the extreme barrier approach of setting the objective to infinity for infeasible points and treatingthe problem as unconstrained.The main GPS convergence result is to identify limit points ˆx, where the Clarke generalizedderivatives are nonnegative in a finite set of directions, called refining directions. Although in theunconstrained case, nonnegative combinations of these directions span the whole space, the fact thatthere can only be finitely many GPS refining directions limits rigorous justification of the barrierapproach to finitely many linear constraints for GPS. The main result of this paper is that the generalMADS framework is flexible enough to allow the generation of an asymptotically dense set of refiningdirections along which the Clarke derivatives are nonnegative.We propose an instance of MADS for which the refining directions are dense in the hypertangentcone at ˆx with probability 1 whenever the iterates associated with the refining directions convergeto a single ˆx. The instance of MADS is compared to versions of GPS on some test problems. Wealso illustrate the limitation of our results with examples.