Exact Moment Representation in Polynomial Optimization

Lorenzo Baldi (1) , Bernard Mourrain (1)

1 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes

We investigate the problem of representation of moment sequences by measures in Polynomial Optimization Problems, consisting in finding the infimum f * of a real polynomial f on a real semialgebraic set S defined by a quadratic module Q. We analyse the exactness of Moment Matrix (MoM) relaxations, dual to the Sum of Squares (SoS) relaxations, which are hierarchies of convex cones introduced by Lasserre to approximate measures and positive polynomials. We show that the MoM relaxation coincides with the dual of the SoS relaxation extended with the real radical of the support of the associated quadratic module Q. We prove that the vanishing ideal of the semialgebraic set S is generated by the kernel of the Hankel operator associated to a generic element of the truncated moment cone for a sufficiently high order of the MoM relaxation. When the quadratic module Q is Archimedean, we show the convergence, in Hausdorff distance, of the convex sets of the MoM relaxations to the convex set of probability measures supported on S truncated in a given degree. We prove the exactness of MoM relaxation when S is finite and when regularity conditions, known as Boundary Hessian Conditions, hold on the minimizers. This implies that MoM exactness holds generically. When the set of minimizers is finite, we describe a MoM relaxation which involves f * , show its MoM exactness and propose a practical algorithm to achieve MoM exactness. We prove that if the real variety of polar points is finite then the MoM relaxation extended with the polar constraints is exact. Effective numerical computations illustrate this MoM exactness property.

Domaines: Algèbre commutative [math.AC]; Géométrie algébrique [math.AG]; Optimisation et contrôle [math.OC]

Lorenzo Baldi, Bernard Mourrain. Exact Moment Representation in Polynomial Optimization. 2021. ⟨hal-03082531v3⟩