On the convergence rates of moment-SOS hierarchies approximation of truncated moment sequences

• 成果类型: Article; Early Access
• 署名作者: Tran, Hoang Anh; Toh, Kim-Chuan
• 署名单位: National University of Singapore; National University of Singapore
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02394-6
• 发表日期: 2026-07-07
• 关键词: polynomial optimization; squares; complexity; SUM

摘要

The moment-SOS hierarchy, which is based on Putinar-type (quadratic module) and Schm & uuml;dgen-type (preordering) sum-of-squares positivity certificates, is a widely applicable framework to address polynomial optimization problems over basic semi-algebraic sets. Recent works show that the convergence rate of this hierarchy over certain simple sets, namely, the unit ball, hypercube, and standard simplex, is of the order O(1/r2) , where r denotes the level of the moment-SOS hierarchy. This paper aims to provide a comprehensive understanding of the convergence rate of the Schm & uuml;dgen-type moment-SOS hierarchy by estimating the Hausdorff distance between the set of truncated pseudo-moment sequences and the set of truncated moment sequences through a projection-based method derived from Tchakaloff's theorem. Our results provide a connection between the convergence rate of the Schm & uuml;dgen-type moment-SOS hierarchy and the & Lstrok;ojasiewicz exponent & Lstrok; of the domain under the compactness assumption, where we establish the convergence rate of O(1/r & Lstrok;) . Consequently, we obtain the convergence rate of O(1/r) for polytopes and sets satisfying the constraint qualification condition, O(1/r) for domains that either satisfy the Polyak-& Lstrok;ojasiewicz condition or are defined by locally strongly convex polynomials. We also use our method to reprove the convergence rate of O(1/r2) for general polynomials over a sphere.