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.
Similar content being viewed by others
References
Abramson M.A., Audet C., Dennis J.E., Le Digabel S.: OrthoMads: a deterministic Mads instance with orthogonal directions. SIAM J. Optim 20, 948–966 (2008)
Audet, C., Dennis, J.E. Jr.: Mesh adaptive direct search algorithms for constrained optimization. SIAM Optim. (2006)
Belitz, P: Applications on multi-dimensional sphere packings: derivative-free optimization. PhD dissertation, University of California, San Diego (2011)
Booker A., Dennis J.R., Frank P., Serafini D., Torczon V., Trosset M.: A rigorous framework for optimization of expensive functions by surrogates. Struct. Multidiscip. Optim. 17, 1–13 (1999)
Conway J.H., Sloane N.J.A.: Sphere Packings, Lattices, and Groups. Springer, Berlin (1998)
Coope I.D., Price C.J.: On the convergence of grid-based methods for unconstrained optimization. SIAM J. Optim. 11, 859–869 (2001)
Cox D.D., John S.: SDO: a statistical method for global optimization. In: Alexandrov, N., Hussaini, M.Y. (eds) Multidisciplinary Design Optimization: State of the Art, pp. 315–329. SIAM, Philadelphia (1997)
Elder, J.F. IV: Global Rd optimization when probes are expensive: the GROPE algorithm. In: Proceedings of the 1992 IEEE International Conference on Systems, Man, and Cybernetics, vol. 1, pp. 577–582. Chicago (1992)
Ermoliev Y.: Numerical Techniques for Stochastic Optimization. Springer, New York (1988)
Fejes Tóth L.: Perfect distribution of points on a sphere. Periodica Mathematica Hungarica 1, 25–33 (1971)
Goldberg D.E.: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading (1989)
Isaaks E.H., Srivastav R.M.: An Introduction to Applied Geostatistics. Oxford University Press, Oxford (1989)
Jones D.R.: A taxonomy of global optimization methods based on response surfaces. J. Global Optim. 21, 345–383 (2001)
Kennedy, J., Eberhart, R: Particle swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks, pp. 1942–1948. v.4. (1995)
Kirkpatrick S., Gelatt C.D. Jr., Vecchi M.P.: Optimization vi simulated annealing. Science 20(4598), 671–680 (1984)
Krige D.G.: A statistical approach to some mine valuations and allied problems at the Witwatersrand. Master’s thesis of the University of Witwatersrand, South Africa (1951)
Kushner H.J.: A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise. J. Basic Eng. 86, 97–106 (1964)
Marsden A.L., Vignon-Clementel I.E., Chan F., Feinstein J.A., Tyalor C.A.: Trailing-edge noise reduction using derivative-free optimization and large-eddy simulation. J. Fluid Mech. 572, 250–263 (2007)
Matheron G.: Principles of geostatistics. Econ. Geol. 58, 1246–1266 (1963)
McKay M.D., Beckman R.J., Conover W.J.: A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Techonometrics 21, 239–245 (1979)
Meschkowski H.: Ungelöste und unlösbare Probleme der Geometrie. Bibliographisches Institut, Mannheim (1960)
Mockus J.: Application of Bayesian approach to numerical methods of global and stochastic optimization. J. Global Optim. 4, 347–365 (1994)
Nelder J.A., Mead R.: A simplex method for function minimization. Comput. J. 7, 308–313 (1965)
Perttunen, C.: A computational geometric approach to feasible region division in constrained global optimization. In: Proceedings of the 1991 IEEE Conference on Systems, Man, and Cybernetics (1991)
Rasmussen C.E., Williams C.K.I.: Gaussian Processes for Machine Learning. MIT Press, Cambridge (2006)
Spendley W., Hext G.R., Himsworth F.R.: Sequential application of simplex designs in optimisation and evolutionary operation. Technometrics 4, 441–461 (1962)
Stuckman B.E.: A global search method for optimizing nonlinear systems. IEEE Trans. Syst. Man Cybern. 18, 965–977 (1988)
Tammes P.M.L.: On the origin of number and arrangement of the places of exit on the surface of pollen-grains. Recueil des travaux botaniques néerlandais 27, 1–84 (1930)
Thomson J.J.: On the structure of the atom: an investigation of the stability and periods of oscillation of a number of corpuscles arranged at equal intervals around the circumference of a circle; with application of the results to the theory of atomic structure. Philos. Mag. Ser. 6 7(39), 237–265 (1904)
Torczon V.: On the convergence of pattern search algorithms. SIAM J. Optim. 7, 1–25 (1997)
Torn A., Zilinskas A.: Global Optimization. Springer, Berlin (1987)
Yang W., Feinstein J.A., Marsden A.L.: Constrained optimization of an idealized Y-shaped baffle for the Fontan surgery at rest and exercise. CMAME 199, 2135–2149 (2010)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Belitz, P., Bewley, T. New horizons in sphere-packing theory, part II: lattice-based derivative-free optimization via global surrogates. J Glob Optim 56, 61–91 (2013). https://doi.org/10.1007/s10898-012-9866-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-012-9866-7