Adaptive probabilistic branch and bound for level set approximation

We present a probabilistic branch-and-bound (PBnB) method for locating a subset of the feasible region that contains solutions in a level set achieving a user-specified quantile. PBnB is designed for optimizing noisy (and deterministic) functions over continuous or finite domains, and provides more information than a single incumbent solution. It uses an order statistics based analysis to guide the branching and pruning procedures for a balanced allocation of computational effort. The statistical analysis also prescribes both the number of points to be sampled within a sub-region and the number of replications needed to estimate the true function value at each sample point. When the algorithm terminates, it returns a concentrated sub-region of solutions with a probability bound on their optimality gap and an estimate of the global optimal solution as a by-product. Numerical experiments on benchmark problems are presented.