Volume of quasi-homogeneous sublevel sets: Two linear algebra deterministic algorithms with convergence rates
Abstract
We study deterministic approximation of the Lebesgue volume of compact unit sublevel sets of positive quasi-homogeneous polynomials. Pushing the uniform measure on a bounding box through the polynomial reduces the problem to a univariate moment problem. Weighted homogeneity determines the moments of its restriction to the unit interval up to the unknown volume. Two algorithms provide upper and lower bounds using polynomial arithmetic and linear algebra. CHEB integrates Chebyshev polynomial approximations of a continuous piecewise-linear function and converges algebraically. GEVP uses two generalized eigenvalue problems and converges exponentially, with a rate governed by an upper bound on the polynomial over the box. Moment preprocessing depends on the dimension, polynomial structure and approximation order. Explicit Stokes dual certificates yield corresponding convergence bounds for the multivariate moment-sums-of-squares hierarchy.
Related
- Deterministic and Random Bipartite Matching on General Networks: Convex Flow Reformulation, Asymptotic Properties, and Fast Algorithms
- R-Linear Convergence of Barzilai-Borwein Methods on Strictly Convex Quadratics via Closed-Cone Homogeneous Dynamics
- Randomized algorithms in numerical linear algebra for scientific computing
- A note on the convergence guarantees of RLT-based algorithms for polynomial optimization
- Monte Carlo Power Iteration Algorithms: Convergence, Analysis and Application to Reactor Criticality Calculations
BibTeX
@misc{henrion2026volume,
title = {{Volume of quasi-homogeneous sublevel sets: Two linear algebra deterministic algorithms with convergence rates}},
author = {Didier Henrion and Jean B Lasserre},
howpublished = {HAL},
year = {2026},
month = jul,
eprint = {2607.29269},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05708227v2},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Volume of quasi-homogeneous sublevel sets: Two linear algebra deterministic algorithms with convergence rates
AU - Didier Henrion
AU - Jean B Lasserre
PY - 2026
DA - 2026/07/31
PB - HAL
UR - https://hal.science/hal-05708227v2
AB - We study deterministic approximation of the Lebesgue volume of compact unit sublevel sets of positive quasi-homogeneous polynomials. Pushing the uniform measure on a bounding box through the polynomial reduces the problem to a univariate moment problem. Weighted homogeneity determines the moments of its restriction to the unit interval up to the unknown volume. Two algorithms provide upper and lower bounds using polynomial arithmetic and linear algebra. CHEB integrates Chebyshev polynomial approximations of a continuous piecewise-linear function and converges algebraically. GEVP uses two generalized eigenvalue problems and converges exponentially, with a rate governed by an upper bound on the polynomial over the box. Moment preprocessing depends on the dimension, polynomial structure and approximation order. Explicit Stokes dual certificates yield corresponding convergence bounds for the multivariate moment-sums-of-squares hierarchy.
ER -