A Sparse Version of Reznick's Positivstellensatz

• 成果类型: Article
• 署名作者: Mai, Ngoc Hoang Anh; Magron, Victor; Lasserre, Jean
• 署名单位: Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1284
• 发表日期: 2023
• 页码: 812-833
• 关键词: polynomial optimization; positive polynomials; Representation theorem; approximation; relaxations; squares; sums

摘要

If f is a positive definite form, Reznick's Positivstellensatz states that there exists k is an element of N such that parallel to x parallel to(2k)(2)f is a sum of squares of polynomials. Assuming that f can be written as a sumof forms Sigma(p)(l=1) f(l), where each fl 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 is an element of N such that f = Sigma(p)(l=1) sigma(l)/H-l(k), where sigma(l) is a sum of squares of polynomials, Hl is a uniform polynomial denominator, and both polynomials sigma(l), H-l involve the same variables as f(l) for each l = 1, ..., p. In otherwords, 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 non-negative 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.