Surrogate-based branch-and-bound algorithms for simulation-based black-box optimization

Optimization and Engineering 2022

Black-box surrogate-based optimization has received increasing attention due to the growing interest in solving optimization problems with embedded simulation data. The main challenge in surrogate-based optimization is the lack of consistently convergent behavior, due to the variability introduced by initialization, sampling, surrogate model selection, and training procedures. In this work, we build-up on our previously proposed data-driven branch-and-bound algorithm that is driven by adaptive sampling and the bounding of not entirely accurate surrogate models. This work incorporates Kriging and support vector regression surrogates, for which different bounding strategies are proposed. A variety of data-driven branching heuristics are also proposed and compared. The key finding of this work is that by bounding fitted, approximate surrogate models, one can employ a branch-and-bound structure that converges to the same optimum despite different initialization of samples and selection and training of a surrogate model. The performance of the algorithm is tested using box-constrained nonlinear benchmark problems with up to ten variables.

Link to Publication