Volume and integration on a convex polytope
I have developed a (recursive) program to compute the exact volume of a
convex polytope in R_n, given by its defining hyperplanes Ax<=b.
The underlying method is based on Euler's identity for homogeneous functions.
In the same vein we have also provided a method for integration of homogeneous functions
on domains also defined by homogeneous functions.
For more details, see :
J.B. Lasserre. An analytical expression and an algorithm for the
volume of a convex polyhedron in Rn", J. Optim. Theor. Appl. 39
(1983), pp. 363--377.
J.B. Lasserre. Integration on a convex polytope, Proc. Amer. Math. Soc. 126 (1998), pp. 2433--2441.
J.B. Lasserre. Integration and homogeneous functions", Proc. Amer. Math. Soc. 127 (1999), pp. 813--818.
J.B. Lasserre and K. Avrachenkov. The multi-dimensional version of $\int_a^b x^pdx$", Amer. Math. Monthly 108 (2001), pp. 151--154.
Our volume algorithm is one of those implemented in the public software
VINCI. which itself the volume
computation module of
polymake, a tool for the algorithmic treatment of convex
polyhedra, developed in the Discrete Geometry group
at the Institute of Mathematics of Technische Universitat, Berlin.
This volume computation occurs in various applications in
Economics, computational complexity analysis, linear systems modeling,
VLSI design, Statistics .... In particular, our volume algorithm (as well as our integration method for homogeneous functions) has also been used
as a brick element in the "natural element method" (NEM), a relatively
recent method for solving partial differential equations, as well as in recent extensions
of finite element methods (X-FEM) for some boundary value problems involving
discontinuities. In the X-FEM, the finite element mesh need not conform to the internal boundaries (cracks, material interfaces, voids, etc.), and hence a single mesh suffices for modeling as well as capturing the evolution of material interfaces and cracks in two- and three-dimensions. Our volume (and integration) algorithm is used in e.g.:
A numerical method for solving partial differential equations on
highly irregular grids, J. Braun and M. Sambridge, Nature 376 (1995), pp. 655-660.
The natural element method in solid mechanics, N. Sukumar, B. Moran, and T. Belytschko,
Int. J. Numer. Meth. Eng. 43 (1998), pp. 839--887.
3. On entropy and clustering in earthquake hypocentre distributions, T. Nicholson, M. Sambridge, O. Gudmunsson. Geophys. J. Int. 142 (2000), 37--51.
4. Computing the Information Content of Decoupled Designs, D.D Frey, E. Jahangir, F. Engelhardt. Research in Engineering Design 12 (2000), 90--102.
Modelling three-dimensional piecewise homogeneous domains using the a-shape-based natural element method. E. Cueto, B. Calvo, M. Doblare. Int. J. Num. Meth. Eng. 54 (2002), 871--897.
Overview and Recent Advances in Natural Neighbour Galerkin Methods
E. Cueto, N. Sukumar, B. Calvo, M.A. Martinez, J. Cegonino, M. Doblare.
Arch. Comput. Meth. Engng, 10 (2003), 307-384.
Numerical integration in Natural Neighbour Galerkin methods, D. Gonzalez, E. Cueto, M.A. Martinez, M. Doblare. Int. J. Num. Meth. Eng. 60 (2004), 2077--2104.
A study of the performance on natural neighbour-based Galerkin methods,
I. Alfaro, J. Yonnet, F. Chinesta, E. Cueto. Int. J. Num. Meth. Eng. 71 (2007), 1436--1465.
Application of the natural element method to finite deformation inelastic problems in isotropic
and fiber-reinforced biological soft tissues,
E. Pena, M.A. Martinez, B. Calvo, M. Doblare. Computer Methods in Applied Mechanics and Engineering 197 (2008), 1983--1996.
Natural Neighbor Interpolation: Critical Assessment and New Contributions
T. Bobach, PhD Thesis, University of Kaiserslautern, Germany, 2008.
Numerical Integration of Polynomials and Discontinuous Functions on Irregular Convex Polygons and Polyhedrons
S.E. Mousavi and N. Sukumar. Computational Mechanics 47 (2011), 535--554.
Generalized Gaussian Quadrature Rules for Discontinuities and Crack Singularities in the Extended Finite Element Method
S.E. Mousavi and N. Sukumar. Computer Methods in Applied Mechanics and Engineering 199 (2010), 3237--3249.
Higher-order extended FEM for weak discontinuities -- level set representation, quadrature and application to magneto-mechanical problems,
M. Kastner, S. Muller, J. Goldmann, C. Spieler, J. Brummund and V. Ulbricht. International Journal for Numerical Methods in Engineering 93 (2013), pp. 1403--1424.
XFEM modeling and homogenization of magnetoactive composites,
C. Spieler, M. Kastner, J. Goldmann, J. Brummund and V. Ulbricht. Acta Mechanica (August 2013).
Natural element method for solving radiative transfer with or without conduction in three-dimensional complex geometries,
Yong Zhang, Yu Ma, Hong-Liang Yi, and He-Ping Tan. Journal of Quantitative Spectroscopy & Radiative Transfer 129 (2013), pp. 118--130.
Higher-order extended FEM for weak discontinuities - level set representation, quadrature and application to
M. Kastner, S. Muller, J. Goldmann, C. Spieler, J. Brummund and V. Ulbricht. Int. J. Numer. Meth. Engng. 93 (2013), 1403--1424.
On the numerical integration of trimmed isogeometric elements.,
A.P. Nagy and D.J. Benson. Comput. Methods Appl. Mech. Engrg. 284 (2015), 165--185.
and also in various other applications like e.g.
Computing the information content of decoupled designs,
D.D. Frey, E. Jahangir, F. Engelhardt. Research in Engineering Design 12 (2000), 90--102.
Convex set symmetry using Blasche addition, H. Zouaki. Pattern Recognition 36 (2003), 753--763.
Bayesian analysis of binary sequences, D.C. Torney. J. Comp. Appl. Math. 175 (2005), 231--243.
Investigation of voxel warping and energy mapping approaches for fast 4D Monte Carlo dose calculations in deformed geometries using VMC++,
E. Heath, F. Tessier, I. Kawrakow. Phys. Med. Biol. 56 (2011), 5187--5202.
Pentahedral volume, chaos and quantum gravity,
H.M. Haggard. Phys. Review D 87 (2013), 044020.
An algorithm for approximating the highest density region in d-space,
M.T. Waltman. Master thesis, Eramus School of Economics, Rotterdam, The Netherlands, 2014
24. Efficient Voronoi volume estimation for DEM simulations of granular materials under confined conditions,
G. Frenning. MethodsX 2 (2015), 79--90.
25. Statistics of energy partitions for many-particle systems in arbitrary dimension,
V. Aquilanti, . Lombardi, M.B. Sevryuk. Regular and Chaotic Dynamics 19 (2014), 318--347.
More recently, I and my colleague E.S. Zeron (Math. Dept.,
INVESTAV-IPN, Mexico) have provided an alternative algorithm,
now based on (multivariate) inverse Laplace transform techniques.
J.B. Lasserre, E.S. Zeron. A Laplace transform algorithm for
the volume of a convex polytope.
Journal of the ACM 48 (2001), pp. 1126--1140.
It has been used recently in e.g.:
1. Time-Bounded Verification of CTMCs against Real-Time Specifications
, T. Chen, M. Diciolla, M. Kwiatkowska, A Mereacre. In
Formal Modeling and Analysis of Timed Systems, Lecture Notes in Computer Science Volume 6919, 2011, pp. 26-42
2. Verification of linear duration properties over continuous-time markov chains,
T. Chen, M. Diciolla, M. Kwiatkowska, A Mereacre. ACM Transactions on Computational Logic 14, No 4 (2013) art. 33
As mentioned, we have also provided algorithms for integration of a polynomial (and more generally, homogeneous functions) on a convex polytope. In particular, our exact formula
J.B. Lasserre and K. Avrachenkov. The multi-dimensional version of $\int_a^b x^pdx$, Amer. Math. Monthly 108 (2001), pp. 151--154,
for integrating a polynomial on a Simplex has been proved very useful in Mesh Clustering; see e.g.:
Mesh Clustering L_P-Centroidal Voronoi Tesselation and its Applications
Fengtao Fan, F. Cheng, C. Huang, Y. Li, J. Wang, S. Lai.,
Proc. SIAM/ACM Joint Conference on Geometrical & Physical Modeling, San Francisco, 2009, pp. 301--306.
L_P-Centroidal Voronoi Tesselation and its Applications
B. Levy, Yang Liu. ACM Trans. Graphics 29, 4, Article 119.
Gradient of the Objective Function for an Anisotropic Centroidal
Voronoi Tessellation (CVT) - A revised, detailed derivation.
G. Parigi, M. Piastra. arXiv:1408.5622v1, 2014,
while our formula
J.B. Lasserre. Integration on a convex polytope, Proc. Amer. Math. Soc. 126 (1998), pp. 2433--2441,
has been recently used to provide efficient cubature formula on trimmed isogeometric elements of arbitrary shape as part of the standard
finite element preprocessing step; see:
On the numerical integration of trimmed isogeometric elements.
A.P. Nagy, D.J. Benson. Computer Methods in Applied Mechanics & Engineering 284, pp. 165--185, 2015.
My colleague Didier
and I, have developed a software called
for the global minimization of a multivariate polynomial
on a semi-algebraic set. This software was among 30 softwares
selected (out of 160) as finalists of the
software competition in Switzerland (September 2004).
The underlying method makes extensive use of recent results from real
algebraic geometry on the representation of polynomials,
positive on a compact semi-algebraic set. For more details, see:
1. Global optimization with polynomials and the problem of
moments, J.B. Lasserre. SIAM J. Optimization 11 (2001), pp 796--817.
2. GloptiPoly : Global optimization over
polynomials with Matlab and SeDuMi, D. Henrion and J.B. Lasserre. ACM Trans. Math. Soft. 29 (2003), pp. 165--194.
3. GloptiPoly 3: Moments, Optimization and Semidfinite Programming, D. Henrion, J.B. Lasserre and Y. Lofberg.
Optimization, Methods and Softwares 24 (2009), pp. 761--779
GloptiPoly has been used in several areas and more recently for solving certain optimization problems in
"Quantum Computing", e.g. in:
Complete hierarchies of efficient approximations to problems in entanglement theory
J Eisert, P Hyllus, O Guhne, M Curty - Physical Review A, 2004
Detecting two-party quantum correlations in quantum-key-distribution protocols
M Curty, O Guhne, M Lewenstein, N Lutkenhaus - Physical Review A, 2005.
Upper bound on the secret key rate distillable from effective quantum correlations with imperfect detectors
T Moroder, M Curty, N Lutkenhaus - Physical Review A, 2006
Intercept-resend attacks in the Bennett-Brassard 1984 quantum-key-distribution protocol with weak coherent pulse
M Curty, N Lutkenhaus - Physical Review A, 2005
Quantifying entanglement with witness operators
Fernando G.S.L. Brandao. Physical Review A 72, 2005.
Deterministic computational complexity of the quantum separability problem
L. Ioannou. Quantum Information and Computation, 2006.
Quantum separability and entanglement detection via entanglement-witness search and global optimization
L. Ioannou, B.C. Travaglione. Physical Review A 73, 2006.
Better Bell-inequality violation by collective measurements
Yeong-Cherng Liang, A.C. Doherty. Physical Review A 73, 2006.
Estimation of the parameters of a bilinear model with applications to submarine detection and system identification
R. Abrahamson, S.M. Kay, P. Stoica. Digital Signal Processing 17 (2007), 756--773.
Gain bandwith optimization in two-pump fiber optical parametric amplifiers under bounded zero-dispersion wavelength fluctuations. N. Wong, K.K.-Y. Wong. Optics Communications 272 (2007), 514--520.
Bounds on quantum correlations in Bell-inequality experiments.
Yeong-Cherng Liang, A. Doherty. Physical Review A 75, 2007.
A paradox in bosonic energy computations via semidefinite programming relaxations.
M. Navascues, A. Garcia-Saez, A. Acin, S. Pironio, M.B. Plenio. New Journal of Physics 15, 2013, 023026..
It is also used:
- for Motion Planning in Robotics: See e.g. the algorithm
Numerical Roadmap Algorithm) and the associated paper:
NUROA: A Numerical Roadmap Algorithm, Reza Iraji, Hamidreza Chitsaz, Proceedings IEEE CDC Conference, Los Angeles, December 2014. arXiv:1403.5384
- For solving the Optimal Power Flow Problem, an important problem for the optimal management of energy networks. See e.g. the recent papers:
1. Advanced optimization methods for power systems,
P. Panciatici, M.C. Campi, S. Garratti, S.H. Low, D.K. Molzhan, A.X. Sun and L. Wehenkel. Proceedings 18th Power Systems Computation Conference, Wroclaw, Poland, August 2014.
2. Sparsity-Exploiting Moment-Based Relaxations of the Optimal Power Flow Problem,
D.K. Molzahn and I.A. Hiskens, IEEE Transactions on Power Systems, 2015. arXiv:1404.5071
3. Global Optimization for power dispatch problems based on theory of moments,
J. Tian, H. Wei and J. Tan, Electrical Power and Energy Systems 71, 2015, pp. 184--194.
Finally concerning the impact of this methodology in Optimization, see for instance:
1. Optimization over polynomials: Selected Topics, M. Laurent, Proceedings of ICM conference, Seoul, 2014.
and especially for its impact in Combinatorial Optimization and Theoretical Computer Science,
2. Sum-of-Squares proofs and the quest toward optimal algorithms, B. Barak and D. Steurer, Proceedings of ICM conference, Seoul, 2014.
POCP is a free Matlab package developed by Didier Henrion, myself and Carlo Savorgnan. It uses GloptiPoly 3, and, optionally, YALMIP. The goal is to help solving nonlinear optimal control problems for which all the problem data are polynomial. POCP reformulates such control problems as an instance of the generalized problem of moments to which one applies a hierarchy of semidefinite relaxations.