Density, Determinacy, Duality and a Regularized Moment-SOS Hierarchy

The standard moment-sum-of-squares (SOS) hierarchy is a powerful method for solving global polynomial optimization problems. However, its convergence relies on Putinar’s Positivstellensatz, which requires the feasible set to satisfy the algebraic Archimedean property. In this paper, we introduce a regularized moment-SOS hierarchy capable of handling problems on unbounded sets or bounded sets violating the Archimedean property. Adopting a functional analysis viewpoint, we rely on the multivariate Carleman condition for measure determinacy rather than algebraic compactness. We prove that finite degree projections of the quadratic module are dense in the cone of positive polynomials with respect to the square norm induced by the measure. Based on these density results, we prove the convergence of a regularized hierarchy without invoking any Positivstellensatz. Furthermore, we propose a penalized formulation of the hierarchy which, combined with Bernstein-Markov inequalities, provides a monotonically non-decreasing sequence of certified lower bounds on the global minimum. The approach is illustrated on several benchmark problems known to be difficult or ill-posed for the standard hierarchy.

Article

Download

View PDF