168. DERIVATIVE-FREE OPTIMIZATION VIA PATTERN SEARCH AND KRIGING SURROGATES

Department: Mechanical & Aerospace Engineering
Research Institute Affiliation: Center for Control Systems and Dynamics (CCSD)
Faculty Advisor(s): Thomas Bewley

Primary Student
Name: Paul Belitz
Email: pbelitz@ucsd.edu
Phone: 541-915-5464
Grad Year: 2010

Abstract
In the optimization of expensive nonconvex functions in which no derivative information is available, the Surrogate Management Framework (SMF) is among the most effective strategies available. The SMF combines a pattern search restricted to an underlying grid discretizing parameter space (to keep function evaluations far apart until convergence is approached) with a global search strategy based on an inexpensive "surrogate" (that is, interpolating) model of the function based on all previous function evaluations. Previous SMF implementations have all been coordinated by an underlying Cartesian grid. However, it is well known that Cartesian grids are far inferior in terms of both uniformity and the configuration of nearest-neighbor points when compared with the available alternative grids (a.k.a. "lattices") developed in the mathematical field of n-dimensional sphere-packing theory. Though the remarkably uniform n-dimensional sphere packings available in n=8 and n=24 dimensions have seen broad applications in deep-space communications (forming the foundation of the efficient self-correcting Golay codes), sphere packings have, to date, not been applied in the field of derivative-free optimization.

Our new software package, "Checkers", is a derivative-free optimization package that effectively implements the SMF algorithm using Kriging surrogates in conjunction with a pattern search coordinated by lattices using from n-dimensional sphere-packings. Preliminary results indicate very substantial improvement in convergence speed when compared to SMF implementations based on the far less regular Cartesian grids.

« Back to Posters or Search Results