Abstract for Optimization 2004
Generating Set Search for Nonlinear Programming

Tamara G. Kolda, Robert Michael Lewis, and Virginia Torczon


Generating Set Search (GSS) defines a class of direct search methods that rely on a set of generators for the cone of feasible descent directions. Using this observation leads to a unifying framework that lends itself to a variety of convergence results. Stationarity results for derivative-free, GSS methods for unconstrained optimization will be the focus of this talk. The principles underlying the analysis for the unconstrained case can be generalized to handle bound constraints and linear constraints, as well as extensions to problems with nonlinear constraints.

A particular measure of stationarity will be shown to be of the same order as the step length at an identifiable subset of the iterations. Thus, even in the absence of explicit knowledge of the derivatives of the objective function, there is information about stationarity. These results help clarify the fundamental geometrical ideas underlying several classes of direct search algorithms. In addition, these results validate a practical stopping criterion for such algorithms and lead to local convergence results.