2024/06/20 by Lei Huang, Huang, Lei
Computer Science · Engineering · Mathematics · #Advanced Algebra and Logic #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2406.13980
openalex publication_date 2024/06/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper studies the complexity of matrix Putinar's Positivstellensätz on the semialgebraic set that is given by the polynomial matrix inequality. \revWhen the quadratic module generated by the constrained polynomial matrix is Archimedean, we prove a polynomial bound on the degrees of terms appearing in the representation of matrix Putinar's Positivstellensätz. Estimates on the exponent and constant are given. As a byproduct, a polynomial bound on the convergence rate of matrix sum-of-squares relaxations is obtained, which resolves an open question raised by Dinh and Pham. When the constraining set is unbounded, we also prove a similar bound for the matrix version of Putinar--Vasilescu's Positivstellensätz by exploiting homogenization techniques.