An Efficient Code for Derivative-free Optimization of Expensive Nonconvex Functions Leveraging Kriging Interpolants and Highly Uniform Background Lattices

Presenter: Paul Belitz (UCSD)
Advisor: Thomas Bewley

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 [though two of the prominant leaders of this mathematical field, Conway and Sloane, identify correctly in their landmark book on the subject that this is a very natural application of this theory]. 

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 based on n-dimensional sphere-packings. Preliminary results indicate very substantial improvement in convergence when compared to SMF implementations based on the far less regular Cartesian grids.