(461f) Optimization of Black-Box Problems Using Smolyak Grids and Polynomial Approximations
The proposed work tests the performance of a new surrogate-based optimization algorithm that is based on Smolyak-grid sampling and polynomial interpolation, which have been predominantly used for numerical integration . The algorithm starts with a global search of the multidimensional space, using a Smolyak grid  which is constructed using Chebyshev extrema in the one-dimensional space. The collected samples are used to fit polynomial interpolants, which are used as surrogates towards the search for the optimum. The developed algorithm adaptively refines the grid by collecting new points in promising regions, and iteratively refines the search space around the incumbent sample until the search domain reaches a minimum size and convergence has been attained. The algorithm is tested on a large set of benchmark problems and its performance is compared to a recent algorithm for global optimization of grey-box problems using quadratic, kriging and radial basis functions . It is shown that the proposed algorithm has a consistently reliable performance for the majority of test problems, which does not depend on the initialization of the sampling set. It will be shown that this reliability in performance is attributed to the use of Chebyshev-based sparse grids, which have been shown to approximate complex functions with low error bounds.
This work is dedicated to the authors' mentor and postdoctoral advisor, Christodoulos Floudas, who introduced the authors to this area.
1. Conn, A.R., K. Scheinberg, and L.N. Vicente, Introduction to derivative-free optimization. 2009, Philadelphia: SIAM.
2. Boukouvala, F., R. Misener, and C.A. Floudas, Global optimization advances in Mixed-Integer Nonlinear Programming, MINLP, and Constrained Derivative-Free Optimization, CDFO. European Journal of Operational Research, 2016. 252(3): p. 701-727
3. Rios, L.M. and N.V. Sahinidis, Derivative-free optimization: a review of algorithms and comparison of software implementations. Journal of Global Optimization, 2013. 56(3): p. 1247-1293
4. Gerstner, T. and M. Griebel, Numerical integration using sparse grids. Numerical Algorithms, 1998. 18(3-4): p. 209-232.
5. Smolyak, S.A. Quadrature and interpolation formulas for tensor products of certain classes of functions. in Dokl. Akad. Nauk SSSR. 1963.
6. Boukouvala, F. and C.A. Floudas, ARGONAUT: AlgoRithms for Global Optimization of coNstrAined grey-box compUTational problems. Optimization Letters, 2016: p. 1-19.