CRPC-TR00814						February 2000

Title: Analysis of Generalized Pattern Searches

Authors: Charles Audet and J. E. Dennis, Jr.

Submitted February 2000

Abstract: This paper contains a new analysis for the Generalized Pattern
Search (GPS) methods of Torczon and Lewis and Torczon. The two novel
aspects are that the proofs are much shorter, and they use weaker
continuity assumptions. Specifically, under very mild conditions, the
method finds an interesting limit point even if the objective function is
not continuous and is even extended valued. If the objective is Lipschitz
near the limit point, then appropriate directional derivatives of the
objective are zero.  If the objective is strictly differentiable at the
limit point, then the gradient exists and is zero.  The results here show
the power of GPS on some classes of real problems better than the previous
analysis for continuously differentiable objectives.

------------------------------------------------------------------------------

Charles Audet           J.E. Dennis Jr.
charlesa@caam.rice.edu  dennis@caam.rice.edu
Department of Computational and Applied Mathematics
Rice University