On the complexity of Putinar-Vasilescu's Positivstellensatz

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,dots,m with g1:=L-|x|22 for some L>0, then there exist positive constants bar c and c depending on f,gj such that for any varepsilon>0, for all k≥ bar c varepsilon-c, f has the decomposition beginequation beginarrayl (1+|x|22)k(f+varepsilon)=σ0+sumj=1m σjgj ,, endarray endequation 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(varepsilon-c) for prescribed accuracy varepsilon>0. In particular, if m=L=1 then c=65, yielding the complexity O(varepsilon-65) for the minimization of a polynomial on the unit ball. Our result improves the complexity bound O(exp(varepsilon-c)) due to Nie and Schweighofer in [Journal of Complexity 23.1 (2007): 135-150].