Title: Practical volume computation of structured convex bodies, and an application to modeling portfolio dependencies and financial crises,
Abstract: We examine volume computation of general-dimensional polytopes and more
general convex bodies, defined as the intersection of a simplex by a family of
parallel hyperplanes, and another family of parallel hyperplanes or a family of
concentric ellipsoids. Such convex bodies appear in modeling and predicting
financial crises. The impact of crises on the economy (labor, income, etc.)
makes its detection of prime interest. Certain features of dependencies in the
markets clearly identify times of turmoil. We describe the relationship between
asset characteristics by means of a copula; each characteristic is either a
linear or quadratic form of the portfolio components, hence the copula can be
constructed by computing volumes of convex bodies. We design and implement
practical algorithms in the exact and approximate setting, we experimentally
juxtapose them and study the tradeoff of exactness and accuracy for speed. We
analyze the following methods in order of increasing generality: rejection
sampling relying on uniformly sampling the simplex, which is the fastest
approach, but inaccurate for small volumes; exact formulae based on the
computation of integrals of probability distribution functions; an optimized
Lawrence sign decomposition method, since the polytopes at hand are shown to be
simple; Markov chain Monte Carlo algorithms using random walks based on the
hit-and-run paradigm generalized to nonlinear convex bodies and relying on new
methods for computing a ball enclosed; the latter is experimentally extended to
non-convex bodies with very encouraging results. Our C++ software, based on
CGAL and Eigen and available on github, is shown to be very effective in up to
100 dimensions. Our results offer novel, effective means of computing portfolio
dependencies and an indicator of financial crises, which is shown to correctly
identify past crises.