An Effective Positivstellensatz over the Rational Numbers for Finite Semialgebraic Sets
Authors:
- Lorenzo BaldiLBLorenzo Baldi
- Térésa KrickTKTérésa Krick
Preprint
Abstract
We study the problem of representing multivariate polynomials with rational coefficients, which are nonnegative and strictly positive on finite semialgebraic sets, using rational sums of squares.We focus on the case of finite semialgebraic sets S defined by equality constraints, generating a zero-dimensional ideal I, and by nonnegative sign constraints.First, we obtain existential results. We prove that a strictly positive polynomial f with coefficients in a subfield K of R has a representation in terms of weighted Sums-of-Squares with coefficients in this field, even if the ideal I is not radical. We generalize this result to the case where f is nonnegative on S and (f ) + (I : f ) = 1. We deduce that nonnegative polynomials with coefficients in K can be represented in terms of Sum-of-Squares of polynomials with coefficients in K, when the ideal is radical.Second, we obtain degree bounds for such Sums-of-Squares representations, which depend linearly on the regularity of the ideal and the degree of the defining equations, when they form a graded basis.Finally, we analyze the bit complexity of the Sums-of-Squares representations for polynomials with coefficients in Q, in the case the ideal is radical. The bitsize bounds are quadratic or cubic in the Bezout bound, and linear in the regularity, generalizing and improving previous results obtained for special zero dimensional ideals.As an application in the context of polynomial optimization, we retrieve and improve results on the finite convergence and exactness of the moment/Sums-of-Squares hierarchy.Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- On the effective Putinar’s Positivstellensatz and moment approximationMathematical Programming, 2022
- Representations of positive polynomials on noncompact semialgebraic sets via KKT idealsJournal of Pure and Applied Algebra, 2007
- On the complexity of Putinar's PositivstellensatzJournal of Complexity, 2007
- Semidefinite representations for finite varietiesMathematical Programming, 2006
- Minimizing Polynomials via Sum of Squares over the Gradient IdealMathematical Programming, 2005
- TheK-moment problem for compact semi-algebraic setsMathematische Annalen, 1991
- Class of global minimum bounds of polynomial functionsCybernetics and Systems Analysis, 1988
- A nullstellensatz and a positivstellensatz in semialgebraic geometryMathematische Annalen, 1974
- Über die Zerlegung definiter Funktionen in QuadrateAbhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 1927
- ber die Darstellung definiter Funktionen durch QuadrateMathematische Annalen, 1906