Convergence rates of moment-sum-of-squares hierarchies for volume approximation of semialgebraic sets

Moment-sum-of-squares hierarchies of semidefinite programs can be used to approximate the volume of a given compact basic semialgebraic set K. The idea consists of approximating from above the indicator function of K with a sequence of polynomials of increasing degree d, so that the integrals of these polynomials generate a convergence sequence of upper bounds on the volume of K. Under certain assumptions, we show that the asymptotic rate of this convergence is at least \(O(1{/}\log \log d)\) in general and \(O(1 / \log d)\) provided that the semialgebraic set is defined by a single inequality.

1. The minimum in (3) is attained since the sets K and X have non-empty interiors and hence the truncated quadratic modules are closed (see [5, Theorem 3.49]) and since the sets \(\{p\in \mathbb {R}[x]_d\mid \int _X p - v_d^\star \le \epsilon \}\) are bounded in the coefficient norm on \(\mathbb {R}[x]_d\) for every \(\epsilon > 0\) (and decreasing with \(\epsilon \rightarrow 0\)). This is because p is nonnegative and hence \(\int _X p\) is equal to its \(L_1\) norm over X and this norm is equivalent to the coefficient norm on the finite-dimensional space \(\mathbb {R}[x]_d\), provided that X has a nonempty interior.

2. Such decomposition is possible since K is basic semialgebraic, i.e., defined by finitely many polynomial inequalities. A constructive way to obtain this decomposition proceeds by enumerating the connected components of the at most \(2^{n_K}\) active sets associated to the \(n_K\) inequalities defining K.

3. We conjecture that based on analogous results in classical Fourier analysis where the Gibbs phenomenon is provably finite (and precisely quantified).

4. By assumption \(K \subset X\) and hence it is sufficient to take K in the definition of r in (7) rather than S.

The authors would like to thank the three anonymous reviewers for their constructive comments that helped improve the manuscript as well as to J. Nie for pointing out that the complexity can be reduced if the semialgebraic set is defined by a single constraint. The research of M. Korda was supported by the Swiss National Science Foundation under Grant P2ELP2_165166.

Authors and Affiliations

1. Department of Mechanical Engineering, University of California, Santa Barbara, CA, 93106-5070, USA

   Milan Korda

2. LAAS, CNRS, 7 avenue du colonel Roche, 31400, Toulouse, France

   Didier Henrion

3. LAAS, Université de Toulouse, 31400, Toulouse, France

   Didier Henrion

4. Faculty of Electrical Engineering, Czech Technical University in Prague, Technická 2, 16626, Prague, Czech Republic

   Didier Henrion

Corresponding author

Correspondence to Milan Korda.

Reprints and permissions