×

Computing Gaussian & exponential measures of semi-algebraic sets. (English) Zbl 1370.28002

Summary: We provide a numerical scheme to approximate as closely as desired the Gaussian or exponential measure \(\mu(\mathbf{\Omega})\) of (not necessarily compact) basic semi-algebraic sets \(\mathbf{\Omega} \subset \mathbb{R}^n\). We obtain two monotone (non-increasing and non-decreasing) sequences of upper and lower bounds \((\overline{\omega}_d)\), \((\underline{\omega}_d)\), \(d \in \mathbb{N}\), each converging to \(\mu(\mathbf{\Omega})\) as \(d \rightarrow \infty\). For each \(d\), computing \(\overline{\omega}_d\) or \(\underline{\omega}_d\) reduces to solving a semidefinite program whose size increases with \(d\). Some preliminary (small dimension) computational experiments are encouraging and illustrate the potential of the method. The method also works for any measure whose moments are known and which satisfies Carleman’s condition.

MSC:

28A75 Length, area, volume, other geometric measure theory
14P10 Semialgebraic sets and related spaces
90C22 Semidefinite programming
65C60 Computational problems in statistics (MSC2010)
65K05 Numerical mathematical programming methods

Software:

SDPA; GloptiPoly

References:

[1] Alfano, S., A numerical implementation of spherical object collision probability, J. Astronaut. Sci., 53 (2005)
[2] Anjos, M.; Lasserre, J. B., Handbook of semidefinite, (Anjos, M.; Lasserre, J. B., Conic and Polynomial Optimization (2012), Springer-Verlag: Springer-Verlag New York) · Zbl 1235.90002
[3] Ash, R., Real Analysis and Probability (1972), Academic Press Inc.: Academic Press Inc. San Diego · Zbl 1381.28001
[4] Barvinok, A. I., Exponential integrals and sums over convex polyhedra, Funct. Anal. Appl., 26, 127-129 (1992) · Zbl 0798.32002
[5] Chan, F. K., Spacecraft Collision Probability (2008), IAA, The Aerospace Press
[6] Chandramouli, R.; Ranganathan, N., Computing the bivariate Gaussian probability integral, IEEE Signal Process. Lett., 6, 129-130 (1999)
[7] Didonato, A. R.; Jarnagin, M. P.; Hageman, R. K., Computation of the integral of the bivariate normal distribution over convex polygons, SIAM J. Sci. Statist. Comput., 1, 179-186 (1980) · Zbl 0454.65014
[8] Federer, H., The Gauss-Green theorem, Trans. Amer. Math. Soc., 58, 44-76 (1945) · Zbl 0060.14102
[9] Fujisawa, K.; Fukuda, M.; Kojima, M.; Nakata, K., Numerical evaluation of SDPA (Semidefinite Programming Algorithm), (High Performance Optimization, Applied Optimization, vol. 33 (2000), Springer: Springer New York), 267-301 · Zbl 0952.90047
[10] Genz, A., Numerical computation of rectangular bivariate and trivariate normal and \(t\) probabilities, Stat. Comput., 14, 151-160 (2004)
[11] Henrion, D.; Lasserre, J. B.; Lofberg, J., Gloptipoly 3: moments, optimization and semidefinite programming, Optim. Methods Softw., 24, 761-779 (2009) · Zbl 1178.90277
[12] Henrion, D.; Lasserre, J. B.; Savorgnan, C., Approximate volume and integration for basic semialgebraic sets, SIAM Rev., 51, 722-743 (2009) · Zbl 1179.14037
[13] Kotz, S.; Johnson, N. L.; Boyd, D. W., Series representation of distribution of quadratic forms in normal variables. I. Central case, Ann. Math. Stat., 38, 823-837 (1967) · Zbl 0146.40906
[14] Kotz, S.; Johnson, N. L.; Boyd, D. W., Series representations of distributions of quadratic forms in normal variables II. Non-central case, Ann. Math. Stat., 38, 838-848 (1967) · Zbl 0146.40906
[15] Lasserre, J. B., Moments, Positive Polynomials and Their Applications (2009), Imperial College Press: Imperial College Press London
[16] Lasserre, J. B., The K-moment problem for continuous functionals, Trans. Amer. Math. Soc., 365, 2489-2504 (2013) · Zbl 1275.44003
[17] Lasserre, J. B., An Introduction to Polynomial and Semi-Algebraic Optimization (2015), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1320.90003
[18] Numerical computation of multivariate normal and multivariate t probabilities over ellipsoidal regions, J. Stat. Softw., 6, 8 (2001)
[19] Patera, R. P., General method for calculating satellite conjunction probability, J. Guid. Control Dyn., 24 (2001)
[20] Ruben, H., Probability content of regions under spherical normal distributions, IV: the distribution of homogeneous and non-homogeneous quadratic functions of normal variables, Ann. Math. Stat., 33, 542-570 (1962) · Zbl 0117.37201
[21] Salvy, B., D-finiteness: algorithms and applications, (Kauers, Manuel, Proceedings of the 18th International Symposium on Symbolic and Algebraic Computation. Proceedings of the 18th International Symposium on Symbolic and Algebraic Computation, Beijing, China, July 24-27, 2005 (2005), ACM Press), 2-3
[22] Serra, R.; Arzelier, D.; Joldes, M.; Lasserre, J. B.; Rondepierre, A.; Salvy, B., Fast and accurate computation of orbital collision probability for short-term encounters, J. Guid. Control Dyn., 39, 1-13 (2016)
[23] Whitney, H., Geometric Integration Theory (1957), Princeton University Press: Princeton University Press Princeton · Zbl 0083.28204
[24] Wright, S., Primal-Dual Interior-Point Methods (1997), SIAM: SIAM Philadelphia, PA · Zbl 0863.65031
[25] Zeilberger, D., A holonomic systems approach to special functions identities, J. Comput. Appl. Math., 32, 321-368 (1990) · Zbl 0738.33001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.