Title: Pattern Search Methods in the Presence of Degeneracy

Pattern search methods are known as optimization techniques that do not explicitly use derivatives. These methods are extremely effective for some engineering design problems with expensive function evaluations when used with less expensive surrogates. For these and many other applied problems, explicit information about derivatives of the objective function may be unavailable or untrustworthy. We begin the talk by briefly summarizing the history of direct search methods and overview of the generalized pattern search (GPS) algorithms. Our focus then turns to 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 previous work, Lewis and Torczon developed a scheme for computing the conforming directions, but it assumed no degeneracy near the current iterate. We discuss constructing the set of directions whether or not the constraints are degenerate. The main difficulty in the degenerate case is in classifying constraints as redundant and nonredundant. We give a short survey of the main definitions and methods for treating redundancy and propose an approach to identify nonredundant constraints, which may be useful for other active set algorithms. We also briefly consider a nonlinear constrained optimization problem with linearly dependent constraint gradients.
Joint work with J. E. Dennis Jr., Rice University, and Mark A. Abramson, Air Force Institute of Technology.