Optimization of black-box problems using Smolyak grids and polynomial approximations

A surrogate-based optimization method is presented, which aims to locate the global optimum of box-constrained problems using input–output data. The method starts with a global search of the n-dimensional space, using a Smolyak (Sparse) 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 global optimum. The proposed 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 hyper-volume and convergence has been attained. The algorithm is tested on a large set of benchmark problems with up to thirty dimensions 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 vast majority of test problems, and this is attributed to the use of Chebyshev-based Sparse Grids and polynomial interpolants, which have not gained significant attention in surrogate-based optimization thus far.