  Bayesian optimization (BO) offers an elegant approach for efficiently
optimizing black-box functions. However, acquisition criteria demand their own
challenging inner-optimization, which can induce significant overhead. Many
practical BO methods, particularly in high dimension, eschew a formal,
continuous optimization of the acquisition function and instead search
discretely over a finite set of space-filling candidates. Here, we propose to
use candidates which lie on the boundary of the Voronoi tessellation of the
current design points, so they are equidistant to two or more of them. We
discuss strategies for efficient implementation by directly sampling the
Voronoi boundary without explicitly generating the tessellation, thus
accommodating large designs in high dimension. On a battery of test problems
optimized via Gaussian processes with expected improvement, our proposed
approach significantly improves the execution time of a multi-start continuous
search without a loss in accuracy.
