Approximate Volume and Integration for

Didier Henrion, Jean B. Lasserre, Carlo Savorgnan2009

TL;DR

This paper introduces a novel deterministic method to approximate the volume and polynomial integrals over compact semi-algebraic sets (which can be non-convex and disconnected). It achieves this by formulating the problem as an infinite-dimensional linear program and then solving a hierarchy of semidefinite or linear programming relaxations. This approach offers a powerful tool for problems where traditional methods struggle.

What Problem Does This Paper Address?

Computing the volume of a set and integrating polynomials over it are fundamental problems with wide-ranging applications. For simple shapes like boxes or simplices, standard techniques exist. However, for more general sets, particularly semi-algebraic sets (defined by polynomial inequalities), these problems become computationally challenging. Existing methods often rely on randomization (like Monte Carlo) or are restricted to convex bodies, especially polytopes. This paper aims to provide a deterministic method that works for any compact semi-algebraic set, regardless of its convexity or connectedness, and can approximate both volume and integrals of polynomials.

Methods

The core of the paper's methodology lies in reformulating the problem of computing the volume (or integrals) as an infinite-dimensional linear program (LP). This LP's unknown is a measure related to the Lebesgue measure on a simple bounding set (like a box or ball) that contains the semi-algebraic set of interest.

The key innovation is then to approximate this infinite-dimensional LP by solving a hierarchy of finite-dimensional semidefinite programs (SDPs) or linear programs (LPs). This hierarchy is built by considering increasing numbers of polynomial moments. Specifically:

  • SDP Hierarchy: The paper proposes a sequence of SDPs, denoted $Q_d$, where $d$ is the degree of the polynomials considered. Solving these SDPs yields upper bounds on the volume (or integrals) that converge to the true value as $d$ increases.
  • LP Hierarchy: An alternative hierarchy of LPs, denoted $L_d$, is also presented, offering a potentially more scalable approach for larger problems.

The convergence of these relaxations to the true volume and moments is guaranteed by results from the theory of the K-moment problem, particularly theorems by Putinar and Krivine. The paper also leverages sums of squares (SOS) polynomials and Positivstellensatz theorems to establish the connection between polynomial positivity and the existence of representing measures.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical experiments on synthetic examples.

Key Insights and Ideas

  • Volume as an LP: The problem of computing the volume of a semi-algebraic set can be elegantly framed as an infinite-dimensional linear program. This provides a new perspective and a foundation for approximation.
  • SDP/LP Hierarchy for Approximation: The paper demonstrates that a sequence of SDPs (or LPs) can effectively approximate the solution to the infinite-dimensional LP. This is a powerful technique for tackling otherwise intractable problems.
  • No Convexity Needed: A crucial insight is that the method's effectiveness does not rely on the convexity of the semi-algebraic set. This significantly broadens its applicability beyond existing methods.
  • Polynomial Basis Matters: Numerical experiments highlight that the choice of polynomial basis (e.g., standard power basis vs. Chebyshev polynomials) significantly impacts the convergence speed and numerical stability of the approximations. Chebyshev polynomials, with their denser root distribution near interval boundaries, tend to perform better.
  • Dual Problem Interpretation: The dual of the SDP relaxation offers an interesting interpretation: it corresponds to finding a polynomial that approximates the indicator function of the set of interest, which explains why computing volumes is inherently difficult.

Key Results

  • Convergence Guarantees: The paper provides theoretical guarantees for the convergence of the SDP and LP hierarchies to the exact volume and moments of the uniform distribution on the semi-algebraic set.
  • Volume Approximation: The method generates monotone sequences of upper (or lower) bounds for the volume, which converge to the true volume. For example, using $p=1$ in the LP formulation directly approximates the volume.
  • Integral Approximation: The methodology extends to approximating integrals of any polynomial over the set, as well as integrals against certain weight functions.
  • Numerical Performance: Experiments show that the method can provide good approximations, especially for lower-dimensional problems. The convergence rate is influenced by the degree of the SDP/LP relaxation and the choice of polynomial basis. For instance, in the single-interval example, approximations improve significantly with increasing degree.

Limitations and Future Work

  • Computational Complexity: The primary limitation is the computational cost associated with solving SDPs. The size of the SDPs grows with the degree of approximation, making the method computationally expensive for high-dimensional problems or high-degree approximations. The authors note that for small dimensions (n=2 or n=3), good approximations can be obtained.
  • Choice of Polynomial Basis: While the paper demonstrates the impact of the polynomial basis, further investigation into optimal basis choices (e.g., trigonometric or multivariate Chebyshev) for various types of semi-algebraic sets is suggested.
  • Numerical Stability: The conditioning of the moment matrices can lead to numerical issues for high-degree SDPs, limiting the achievable accuracy.
  • Future Work: The authors suggest exploring alternative polynomial bases for better convergence and investigating the LP hierarchy for larger-scale problems. Further research into the theoretical underpinnings and practical implementation for more complex sets is also implied.

Summary updated

Abstract

Given a basic compact semialgebraic set K ⊂ R n , we introduce a methodology that gen- erates a sequence converging to the volume of K. This sequence is obtained from optimal values of a hierarchy of either semidefinite or linear programs. Not only the volume but also every finite vector of moments of the probability measure that is uniformly distributed on K can be approximated as closely as desired, which permits the approximation of the integral on K of any given polynomial; the extension to integration against some weight functions is also provided. Finally, some numerical issues associated with the algorithms involved are briefly discussed.
BibTeX
@misc{henrion2009approximate,
  author = {Didier Henrion and Jean B. Lasserre and Carlo Savorgnan},
  title = {{Approximate Volume and Integration for}},
  year = {2009},
}
Figure