Volume computation of convex regions

Exact volume computation of convex polytopes is #P hard. Polynomial-time randomized approximation algorithms have been developed, with ever-improving complexity bounds, ever since the breakthrough of Dyer, Frieze and Kannan in 1991. Following subsequent work by Lovasz and co-workers, we present the first practical method based on Markov chain Monte Carlo algorithms for uniform sampling by means of geometric random walks. Our public-domain software uses the well-established approach of Hit-and-Run and proves to be effective for dimensions in the hundreds. We thus show that worst-case asymptotic bounds are overly pessimistic. Moreover, our approach is extended toExact volume computation of convex polytopes is #P hard. Polynomial-time randomized approximation algorithms have been developed, with ever-improving complexity bounds, ever since the breakthrough of Dyer, Frieze and Kannan in 1991. Following subsequent work by Lovasz and co-workers, we present the first practical method based on Markov chain Monte Carlo algorithms for uniform sampling by means of geometric random walks. Our public-domain software uses the well-established approach of Hit-and-Run and proves to be effective for dimensions in the hundreds. We thus show that worst-case asymptotic bounds are overly pessimistic. Moreover, our approach is extended to convex non-polyhedral regions and, experimentally, to non-convex bodies with encouraging results.

We then examine structured convex bodies that can be defined as the intersection of a simplex and families of parallel hyperplanes, or concentric ellipsoids. They appear in modeling and predicting financial crises by capturing the relationship between financial characteristics of portfolios by a copula. Input structure allows us to employ more specific methods, ranging from rejection sampling that relies on sampling the simplex, up to exact formulae based on the computation of integrals of probability distribution functions, when intersecting the simplex with a single hyperplane.  convex non-polyhedral regions and, experimentally, to non-convex bodies with encouraging results.

We then examine structured convex bodies that can be defined as the intersection of a simplex and families of parallel hyperplanes, or concentric ellipsoids. They appear in modeling and predicting financial crises by capturing the relationship between financial characteristics of portfolios by a copula. Input structure allows us to employ more specific methods, ranging from rejection sampling that relies on sampling the simplex, up to exact formulae based on the computation of integrals of probability distribution functions, when intersecting the simplex with a single hyperplane.