Large-Scale Discrete Constrained Black-Box Optimization Using Radial Basis Functions

Relatively few surrogate-based methods have been developed for constrained expensive black-box optimization with discrete variables. Even more scarce are surrogate methods that can also be used for high-dimensional problems with hundreds of discrete variables. This paper develops the CONDOR algorithm for large-scale computationally expensive constrained optimization problems with ordinal discrete variables and many black-box inequality constraints. The algorithm builds multiple response surface or surrogate models to approximate the objective function and each of the constraint functions. The response surface models identify promising sample points for function evaluations from a large number of trial points in the neighborhood of the current best solution. The generation of trial points is controlled by two parameters, the probability of perturbing a variable and a depth parameter, which provides the maximum amount of discrete perturbation for each variable. Global and local variants of CONDOR are implemented using radial basis function (RBF) surrogates and are applied to a single-objective version of the large-scale Mazda benchmark problem with 222 discrete variables and 54 black-box inequality constraints using a simulation budget of only 10 times the number of decision variables. The CONDOR algorithms dramatically outperform global and local variants of an RBF-assisted Constrained Discrete Random Search method, the direct search method NOMAD and a genetic algorithm with various crossover fractions and yields a substantial improvement over an initial feasible design on the Mazda benchmark given the limited computational budget.