Pattern search in the presence of degenerate linear constraints

This paper deals with generalized pattern search (GPS) algorithms for linearly constrained optimization. At each iteration, the GPS algorithm generates a set of directions that conforms to the geometry of any nearby linear constraints. This set is then used to construct trial points to be evaluated during the iteration. In a previous work, Lewis and Torczon developed a scheme for computing the conforming directions, however, the issue of degeneracy merits further investigation. The contribution of this paper is to provide a detailed algorithm for constructing the set of directions whether or not the constraints are degenerate. One difficulty in the degenerate case is the classification of constraints as redundant or nonredundant. We give a short survey of the main definitions and methods for treating redundancy and propose an approach to identify nonredundant ϵ-active constraints. We also introduce a new approach for handling nonredundant linearly dependent constraints, which maintains GPS convergence properties without significantly increasing computational cost. Some simple numerical tests illustrate the effectiveness of the algorithm. Keywords: pattern searchlinearly constrained optimizationderivative-free optimizationdegeneracy; redundancyconstraint classificationAMS Subject Classifications: 90C5690C3065K0549M30 Acknowledgements The research of the third author was supported in part by AFOSR F49620-01-1-0013, the Boeing Company, Sandia CSRI, ExxonMobil, the LANL Computer Science (LACSI) contract 03891-99-23, by the Institute for Mathematics and its Applications with funds provided by the National Science Foundation and by funds from the Ordway Endowment at the University of Minnesota. This work was begun at the IMA, where Olga Brezhneva was a postdoctoral fellow, John Dennis was a long-term visitor, and Mark Abramson was a short-term visitor. We thank the IMA for providing such a fine atmosphere for collaboration. We also thank Charles Audet for many useful discussions and two anonymous referees for helpful suggestions. The views expressed in this paper are those of the authors and do not reflect the official policy or position of the United States Air Force, Department of Defense, United States Government, or research sponsors.