On the effective Putinar's Positivstellensatz and moment approximation

• 成果类型: Article
• 署名作者: Baldi, Lorenzo; Mourrain, Bernard
• 署名单位: Universite Cote d'Azur
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01877-6
• 发表日期: 2023
• 页码: 71-103
• 关键词: positive polynomials; complexity; optimization

摘要

We analyse the representation of positive polynomials in terms of Sums of Squares. We provide a quantitative version of Putinar's Positivstellensatz over a compact basic semialgebraic set S, with a new polynomial bound on the degree of the positivity certificates. This bound involves a Lojasiewicz exponent associated to the description of S. We show that if the gradients of the active constraints are linearly independent on S (Constraint Qualification condition), this Lojasiewicz exponent is equal to 1. We deduce the first general polynomial bound on the convergence rate of the optima in Lasserre's Sum-of-Squares hierarchy to the global optimum of a polynomial function on S, and the first general bound on the Hausdorff distance between the cone of truncated (probability) measures supported on S and the cone of truncated pseudo-moment sequences, which are positive on the quadratic module of S.