New horizons in sphere-packing theory, part II: lattice-based derivative-free optimization via global surrogates

Paul Belitz () and Thomas Bewley ()

Journal of Global Optimization, 2013, vol. 56, issue 1, 91 pages

Abstract: Derivative-free algorithms are frequently required for the optimization of nonsmooth scalar functions in n dimensions resulting, for example, from physical experiments or from the statistical averaging of numerical simulations of chaotic systems such as turbulent flows. The core idea of all efficient algorithms for problems of this type is to keep function evaluations far apart until convergence is approached. Generalized pattern search (GPS) algorithms, a modern class of methods particularly well suited to such problems, accomplish this by coordinating the search with an underlying grid which is refined, and coarsened, as appropriate. One of the most efficient subclasses of GPS algorithms, known as the surrogate management framework (SMF; see Booker et al. in Struct Multidiscip Optim 17:1–13, 1999 ), alternates between an exploratory search over an interpolating function which summarizes the trends exhibited by existing function evaluations, and an exhaustive poll which checks the function on neighboring points to confirm or confute the local optimality of any given candidate minimum point (CMP) on the underlying grid. The original SMF algorithm implemented a GPS step on an underlying Cartesian grid, augmented with a Kriging-based surrogate search. Rather than using the n-dimensional Cartesian grid (the typical choice), the present work introduces for this purpose the use of lattices derived from n-dimensional sphere packings. As reviewed and analyzed extensively in Part I of this series (see Belitz, PhD dissertation, University of California, San Diego, 2011 , Chap. 2), such lattices are significantly more uniform and have many more nearest neighbors than their Cartesian counterparts. Both of these facts make them far better suited for coordinating GPS algorithms, as demonstrated here in a variety of numerical tests. Copyright Springer Science+Business Media, LLC. 2013

Keywords: N-dimensional sphere-packing theory; Generalized pattern search; Derivative-free optimization; Global optimization; Surrogate-based methods; Kriging interpolation (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10898-012-9866-7 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:56:y:2013:i:1:p:61-91

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-012-9866-7

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().