A Sparse Version of Reznick’s Positivstellensatz

Ngoc Hoang Anh Mai (), Victor Magron () and Jean Lasserre ()
Additional contact information
Ngoc Hoang Anh Mai: Centre National de la Recherche Scientifique, Laboratory for Analysis and Architecture of Systems, F-31400 Toulouse; France
Victor Magron: Centre National de la Recherche Scientifique, Laboratory for Analysis and Architecture of Systems, F-31400 Toulouse; France
Jean Lasserre: Centre National de la Recherche Scientifique, Laboratory for Analysis and Architecture of Systems, F-31400 Toulouse; France

Mathematics of Operations Research, 2023, vol. 48, issue 2, 812-833

Abstract: If f is a positive definite form, Reznick’s Positivstellensatz states that there exists k ∈ N such that ‖ x ‖ 2 2 k f is a sum of squares of polynomials. Assuming that f can be written as a sum of forms ∑ l = 1 p f l , where each f l depends on a subset of the initial variables, and assuming that these subsets satisfy the so-called running intersection property , we provide a sparse version of Reznick’s Positivstellensatz. Namely, there exists k ∈ N such that f = ∑ l = 1 p σ l / H l k , where σ l is a sum of squares of polynomials, H l is a uniform polynomial denominator, and both polynomials σ l , H l involve the same variables as f l for each l = 1 , … , p . In other words, the sparsity pattern of f is also reflected in this sparse version of Reznick’s certificate of positivity. We next use this result to also obtain positivity certificates for (i) polynomials nonnegative on the whole space and (ii) polynomials nonnegative on a (possibly noncompact) basic semialgebraic set, assuming that the input data satisfy the running intersection property. Both are sparse versions of a positivity certificate from Putinar and Vasilescu.

Keywords: Primary: 90C22; 90C23; Reznick’s Positivstellensatz; sparsity pattern; positive definite forms; running intersection property; sums of squares; Putinar–Vasilescu’s Positivstellensatz; uniform denominators; basic semialgebraic set (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1284 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:2:p:812-833

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().