A Computational Study of Probabilistic Branch and Bound with Multilevel Importance Sampling

Probabilistic branch and bound (PBnB) is a partition-based algorithm developed for level set approximation, where investigating all subregions simultaneously is a computational costly sampling scheme. In this study, we hypothesize that focusing branching and sampling on promising subregions will improve the efficiency of the PBnB algorithm. Two variations to Original PBnB are proposed: Multilevel PBnB and Multilevel PBnB with Importance Sampling. Multilevel PBnB focuses its branching on promising subregions that are likely to be maintained or pruned, as opposed to Original PBnB that branches more subregions. Multilevel PBnB with Importance Sampling attempts to further improve this efficiently by combining focused branching with a posterior distribution that updates iteratively. We present numerical experiments using benchmark functions to compare the performance of each PBnB variation.