# On the complexity of Putinar-Vasilescu's Positivstellensatz

arXiv: https://arxiv.org/abs/2104.11606 · HTML: https://mlsanity.com/paper/2104.11606/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2021.

## Built on by (most cited first, 1 of 1)

- [Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant](https://mlsanity.com/paper/2209.06175/) (2022)

## Abstract (arXiv)

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].