Adaptive Lower Bounds for Gaussian Measures of Polytopes

In this paper, we address the problem of probability mass computation of a multivariate Gaussian contained within a polytope. This computation requires an evaluation of a multivariate definite integral of the Gaussian, whose solution is not tractable for higher dimensions in a reasonable amount of time. Thus, research concentrates on the derivation of approximate but sufficiently fast computation methods. We propose a novel approach that approximates the underlying integration domain, namely the polytope, using disjoint sectors such that the probability mass contained within the sectors is maximized. In order to derive our main algorithm, we first propose an approach to approximate volume computation of a polytope using disjoint sectors. This solution is then extended to the computation of the probability mass of a Gaussian contained within the polytope. The presented solution provides a lower bound on the true probability mass contained within the polytope. Because the initial optimization problem is highly nonlinear, we propose a greedy algorithm that splits the sectors with the highest probability mass.