A sparse version of Reznick's Positivstellensatz - LAAS - Laboratoire d'Analyse et d'Architecture des Systèmes Accéder directement au contenu
Article Dans Une Revue Mathematics of Operations Research Année : 2022

A sparse version of Reznick's Positivstellensatz

Résumé

If $f$ is a positive definite form, Reznick's Positivstellensatz [Mathematische Zeitschrift. 220 (1995), pp. 75--97] states that there exists $k\in\mathbf{N}$ such that ${\| x \|^{2k}_2}f$ is a sum of squares of polynomials. Assuming that $f$ can be written as a sum of forms $\sum_{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 {\em running intersection property}, we provide a sparse version of Reznick's Positivstellensatz. Namely, there exists $k \in \mathbf{N}$ such that $f=\sum_{l = 1}^p {{\sigma_l}/{H_l^{k}}}$, where $\sigma_l$ is a sum of squares of polynomials, $H_l$ is a uniform polynomial denominator, and both polynomials $\sigma_l,H_l$ involve the same variables as $f_l$, for each $l=1,\dots,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 non-compact) basic semialgebraic set, assuming that the input data satisfy the running intersection property. Both are sparse versions of a positivity certificate due to Putinar and Vasilescu.

Dates et versions

hal-02477339 , version 1 (13-02-2020)

Identifiants

Citer

N. H. A. Mai, Victor Magron, Jean-Bernard Lasserre. A sparse version of Reznick's Positivstellensatz. Mathematics of Operations Research, 2022, ⟨10.1287/moor.2022.1284⟩. ⟨hal-02477339⟩
59 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More