A lattice-based approach to derivative-free optimization

The optimization of an expensive, high-dimensional function when no derivative information is available necessitates the use of a derivative-free optimization algorithm. Such a scenario is evident, for example, when optimizing a finite-time-average approximation of an infinite-time-average statistic of a chaotic system such as a turbulent flow. The truncation error induced by such an approximation renders the calculation of the derivative ineffective. Due to the often significant expense associated with performing repeated function evaluations, a derivative-free optimization algorithm which converges to within an accurate tolerance of the global minimum of a nonconvex function of interest with a minimum number of function evaluations is desired. One of the most efficient algorithms available, known as the Surrogate Management Framework, combines a grid-based pattern search Poll step with inexpensive interpolating ``surrogate'' functions to provide suggested regions of parameter space in which to perform new function evaluations. The present work considers an SMF algorithm that combines a pattern search based on N-dimensional sphere packings, or lattices, with a highly efficient surrogate search. The lattice-based Poll step offers substantially greater efficiency compared to previous Cartesian grid-based algorithms; combined with an extremely effective Search, a unique, highly efficient SMF algorithm has been devised.