Accelerated Random Search for constrained global optimization assisted by Radial Basis Function surrogates

The Accelerated Random Search (ARS) algorithm (Appel et al., 2004) is a stochastic algorithm for the global optimization of black-box functions subject only to bound constraints. ARS iteratively samples uniformly within a box centered at the current best point. If the sample point is worse than the current best point, then the size of the box is reduced, thereby making it more likely to generate an improving solution if the current best point is not yet a local minimum. Otherwise, if the sample point is an improvement over the current best point, then the size of the box is reset to the initial value so that the box covers the entire search space. ARS has been shown theoretically and numerically to converge to the global minimum faster than the Pure Random Search (PRS) algorithm on bound-constrained problems. This article develops the Constrained ARS (CARS) algorithm, which is an extension of ARS for optimization problems with black-box inequality constraints. Under some mild conditions on the constrained optimization problem, we prove the convergence to the global minimum in a probabilistic sense of a class of stochastic search algorithms called Scattered Uniform Random Search (SCAT-URS) algorithms, which includes CARS as a special case. To improve performance of CARS on computationally expensive simulation-based problems, we incorporate Radial Basis Function (RBF) surrogate models to approximate the objective and constrained functions, and refer to the resulting algorithm as CARS-RBF. Numerical experiments show that CARS consistently and substantially outperforms both the Pure Random Search (PRS) and Accelerated Particle Swarm Optimization (APSO) algorithms (Yang, 2010) on 31 test problems with dimensions ranging from 2 to 20. Moreover, CARS-RBF is an improvement over CARS, outperforms a sequential penalty derivative-algorithm, and competes with ConstrLMSRBF (Regis, 2011) on the same test problems. Finally, sensitivity analysis of CARS-RBF to the type of RBF model used shows that the cubic RBF model generally yields the best results on the test problems among six types of RBF models considered, including the thin plate spline, Gaussian and multiquadric models.