  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 d_f$
nonnegative on a semialgebraic set having nonempty interior defined by finitely
many polynomial inequalities $g_j(x)\ge 0$, $j=1,\dots,m$ with
$g_1:=L-\|x\|_2^2$ for some $L>0$, then there exist positive constants $\bar c$
and $c$ depending on $f,g_j$ such that for any $\varepsilon>0$, for all $k\ge
\bar c \varepsilon^{-c}$, $f$ has the decomposition \begin{equation}
\begin{array}{l} (1+\|x\|_2^2)^k(f+\varepsilon)=\sigma_0+\sum_{j=1}^m
\sigma_jg_j \,, \end{array} \end{equation} for some SOS polynomials $\sigma_j$
being such that the degrees of $\sigma_0,\sigma_jg_j$ are at most $2(d_f+k)$.
Here $\|\cdot\|_2$ denotes the $\ell_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 $\mathcal{O}(\varepsilon^{-c})$ for prescribed accuracy
$\varepsilon>0$. In particular, if $m=L=1$ then $c=65$, yielding the complexity
$\mathcal{O}(\varepsilon^{-65})$ for the minimization of a polynomial on the
unit ball. Our result improves the complexity bound
$\mathcal{O}(\exp(\varepsilon^{-c}))$ due to Nie and Schweighofer in [Journal
of Complexity 23.1 (2007): 135-150].
