2021/04/23 by Ngoc Hoang Anh, Victor Magron, Mai, Ngoc Hoang Anh +2
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Algebraic Geometry (math.AG) #Commutative Algebra and Its Applications #FOS: Mathematics #Optimization and Control (math.OC) #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2104.11606
openalex publication_date 2021/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We provide a new degree bound on the weighted sum-of-squares (SOS) polynomials for Putinar-Vasilescu's Positivstellensatz. This leads to another Positivstellensatz saying that if f is a polynomial of degree at most 2 df nonnegative on a semialgebraic set having nonempty interior defined by finitely many polynomial inequalities gj(x)≥ 0, j=1,…,m with g1:=L-‖x‖22 for some L>0, then there exist positive constants c and c depending on f,gj such that for any ε>0, for all k≥ c ε-c, f has the decomposition (1+‖x‖22)k(f+ε)=σ0+∑j=1m σjgj , for some SOS polynomials σj being such that the degrees of σ0,σjgj are at most 2(df+k). Here ‖⋅‖2 denotes the ℓ2 vector norm. As a consequence, we obtain a converging hierarchy of semidefinite relaxations for lower bounds in polynomial optimization on basic compact semialgebraic sets. The complexity of this hierarchy is O(ε-c) for prescribed accuracy ε>0. In particular, if m=L=1 then c=65, yielding the complexity O(ε-65) for the minimization of a polynomial on the unit ball. Our result improves the complexity bound O(exp(ε-c)) due to Nie and Schweighofer in [Journal of Complexity 23.1 (2007): 135-150].