Non-SOS Positivstellensätze for semi-algebraic sets defined by polynomial matrix inequalities
Feng Guo · 2025
Read Non-SOS Positivstellensätze for semi-algebraic sets defined by polynomial matrix inequalities by Feng Guo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-01159.txt.
Introduction
Feng Guo proves new results about polynomials that stay positive on sets defined by matrix inequalities. Such results, called Positivstellensatze in German, give certificates that prove a polynomial is positive without checking every point. Guo extends two classic scalar theorems, by Handelman and by Krivine and Stengle, into the matrix setting.
The certificates Guo derives avoid sums of squares and instead use Kronecker powers of the defining matrix with positive semidefinite coefficient matrices. Under a sparsity pattern, leaner certificates also exist, cutting computation cost. Guo then applies the theory to polynomial optimization, building a ladder of relaxations whose size depends on the matrix dimension, not the number of variables. That trait could keep large problems within reach.
Catalog record
| CREATOR | Feng Guo |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 83 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-01159
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Non-SOS Positivstellensätze for semi-algebraic sets defined by polynomial matrix inequalities Thanks: Submitted to the editors DATE. Feng Guo Abstract This paper establishes new Positivstellensätze for polynomials that are positive on sets defined by polynomial matrix inequalities (PMIs). We extend the classical Handelman and Krivine–Stengle theorems from the scalar inequality setting to the matrix context, deriving explicit certificate forms that do not rely on sums-of-squares (SOS). Specifically, we show that under certain conditions, any polynomial positive on a PMI-defined semialgebraic set admits a representation using Kronecker powers of the defining matrix (or its dilated form) with positive semidefinite coefficient matrices. Under correlative sparsity pattern, we further prove more efficient, sparse representations that significantly reduce computational complexity. By applying these results to polynomial optimization with PMI constraints, we construct a hierarchy of semidefinite programming relaxations whose size depends only on the dimension of the constraint matrix, and not on the number of variables. Consequently, our relaxations may remain computationally feasible for problems with large number of variables and low-dimensional matrix constraints, offering a practical alternative where the traditional SOS-based relaxations become intractable. keywords Positivstellensätze, polynomial matrix inequality, Handelman Positivstellensatz, Krivine–Stengle Positivstellensatz, correlative sparsity, semidefinite programming, polynomial optimization Funding. Feng Guo was supported by the Chinese National Natural Science Foundation under grant 12471478. † † runningheads: Non-SOS Positivstellensätze for semialgebraic sets defined by PMIs / F. Guo MSC 90C23, 90C22, 90C26, 14P10, 13J30 1 Introduction Positivstellensätze are fundamental results in real algebraic geometry, offering constructive certificates for the positivity of a polynomial over a semialgebraic set [ 5 , 26 , 29 , 38 ] . These powerful results have widespread applications in areas like optimization, algebraic geometry, control theory, and more where polynomial positivity is a key concern [ 4 , 12 , 24 , 26 , 30 ] . Typically, Positivstellensätze characterize a polynomial f(x)\in{\mathbb{R}}[{\boldsymbol{x}}]:={\mathbb{R}}[x_{1},\ldots,x_{n}] that is positive on a basic semialgebraic set \{{\boldsymbol{x}}\in{\mathbb{R}}^{n}\mid g_{j}({\boldsymbol{x}})\geq 0,j=1,\ldots,s\}, (1) where g_{1},\ldots,g_{s}\in{\mathbb{R}}[{\boldsymbol{x}}] . Many such results achieve this by expressing the polynomial using sums of squares (SOS) structures. For instance, under the assumption that the set ( 1 ) is compact, Schmüdgen [ 40 ] showed that any polynomial f positive on the set ( 1 ) belongs to the preordering generated by g_{j} ’s–that is, it can be written as an SOS-weighted combination of cross-products of g_{j} ’s. Putinar’s Positivstellensatz [ 33 ] provides an alternative representation that avoids the need for cross-products of g_{j} ’s under the Archimedean condition (slightly stronger than compactness). Building on Putinar’s Positivstellensatz, Lasserre [ 20 , 23 , 24 ] introduced the well-known moment-SOS hierarchy of semidefinite programming (SDP) relaxations for polynomial optimization. Reznick [ 36 ] proved that after be multiplying by some power of \sum_{i=1}^{n}x_{i}^{2} , any positive definite form is a sum of even powers of linear forms. Putinar and Vasilescu [ 34 ] extended Reznick’s result to the constrained case where f and g_{j} ’s are homogeneous polynomial of even degree. There also exist several non-SOS structured Positivstellensätze. Pólya [ 31 ] demonstrated that if f is homogeneous and positive on {\mathbb{R}}^{n}_{+}\setminus\{\mathbf{0}\} , then multiplying f by some power of \sum_{i=1}^{n}x_{i} , one obtains a polynomial with nonnegative coefficients. Dickinson and Povh [ 8 ] generalized Pólya’s Positivstellensatz for homogeneous polynomials being positive on the intersection of {\mathbb{R}}^{n}_{+}\setminus\{\mathbf{0}\} and the set ( 1 ), where g_{j} ’s are assumed to be also homogeneous. By replacing SOS polynomials by sums of non-negative circuit polynomials and sums of arithmetic-geometric mean exponential functions, non-SOS Schmüdgen-type and Putinar-type Positivstellensätze have been derived in [ 6 , 10 , 37 ] . When the set ( 1 ) is a compact polyhedron with non-empty interior, Handelman’s Positivstellensatz [ 11 ] states that any polynomial f positive on the set ( 1 ) can be expressed as f({\boldsymbol{x}})=\sum_{{\boldsymbol{\alpha}}\in\mathbb{N}^{s}}\lambda_{{\boldsymbol{\alpha}}}g_{1}({\boldsymbol{x}})^{\alpha_{1}}\cdots g_{s}({\boldsymbol{x}})^{\alpha_{s}}, (2) for some (finitely many) nonnegative scalars \{\lambda_{{\boldsymbol{\alpha}}}\} . In general, assuming that 0\leq g_{i}({\boldsymbol{x}})\leq 1 on the set ( 1 ) for every i , and the family \{1,g_{1},\ldots,g_{s}\} generates {\mathbb{R}}[{\boldsymbol{x}}] , Krivine-Stengle’s Positivstellensatz [ 19 , 41 ] (see also [ 43 ] ) asserts that a positive polynomial f on the set ( 1 ) admits a representation of the form f({\boldsymbol{x}})=\sum_{{\boldsymbol{\alpha}},{\boldsymbol{\beta}}\in\mathbb{N}^{s}}\delta_{{\boldsymbol{\alpha}},{\boldsymbol{\beta}}}g_{1}({\boldsymbol{x}})^{\alpha_{1}}(1-g_{1}({\boldsymbol{x}}))^{\beta_{1}}\cdots g_{s}({\boldsymbol{x}})^{\alpha_{s}}(1-g_{s}({\boldsymbol{x}}))^{\beta_{s}}, (3) for some (finitely many) nonnegative scalars \{\delta_{{\boldsymbol{\alpha}},{\boldsymbol{\beta}}}\} . As an alternative to the moment-SOS relaxations for polynomial optimization, Lasserre [ 21 , 22 ] proposed the linear programming (LP) relaxations by leveraging the representations ( 2 ) and ( 3 ). Most Positivstellensätze could be generalized to the matrix setting. A matrix version of Handelman’s Positivstellensatz was proposed in [ 27 ] to characterize a symmetric polynomial matrix that is positive definite on the set ( 1 ). Using the class of SOS polynomial matrices, Scherer and Hol [ 39 ] developed a matrix analogue of Putinar’s Positivstellensatz for polynomial matrices positive definite (PD) on a set defined by a polynomial matrix inequality (PMI): \mathbf{K}:=\{{\boldsymbol{x}}\in{\mathbb{R}}^{n}\mid G({\boldsymbol{x}})\succeq 0\}, (4) where G is a q\times q symmetric polynomial matrix. Building on this, Dinh et al. [ 9 ] generalized the classical Schmüdgen, Putinar-Vasilescu, and Dickinson–Povh Positivstellensätze to the polynomial matrix setting. Given the projections of two PMI-defined semialgebraic sets, Klep and Nie [ 17 ] provided a matrix Positivstellensatz with lifting polynomials to determine whether one is contained in the other. These generalizations have a wide range of applications, particularly in areas such as optimal control, systems theory [ 13 , 14 , 16 , 32 , 42 ] . Contributions. In this paper, we establish non-SOS Positivstellensätze for characterizing a polynomial f({\boldsymbol{x}})\in{\mathbb{R}}[{\boldsymbol{x}}] that is positive on the PMI-defined semialgebraic set \mathbf{K} . Our results extend the classical Positivstellensätze of Handelman ( 2 ) and Krivine-Stengle ( 3 )–which apply to semialgebraic sets defined by finitely many scalar polynomial inequalities–to the matrix-valued setting. (i) We first consider the case when G({\boldsymbol{x}}) is linear in {\boldsymbol{x}} . Assuming that \mathbf{K} is compact and has nonempty interior, we prove that if f({\boldsymbol{x}}) is positive on \mathbf{K} , then it has the representation f({\boldsymbol{x}})=\lambda_{0}+\sum_{k=1}^{m}\left\langle\Lambda_{k},G({\boldsymbol{x}})^{\otimes k}\right\rangle (5) for some m\in\mathbb{N} , nonnegative number \lambda_{0} and {q^{k}}\times{q^{k}} positive semidefinite (PSD) matrices \Lambda_{k} , k=1,\ldots,m (Theorem 15 ). (ii) Then we extend the result to the nonlinear case. Assume that \mathbf{K} is compact and I_{q}-G({\boldsymbol{x}})\succeq 0 on \mathbf{K} ( I_{q} denotes the q\times q identity matrix), and that {\mathbb{R}}[{\boldsymbol{x}}] can be generated by \{I_{q},G({\boldsymbol{x}})\} (in the sense of Assumption 17 (ii)), we prove that if f({\boldsymbol{x}}) is positive on \mathbf{K} , then it can be written as \lambda_{0}+\sum_{k=1}^{m}\left\langle\Lambda_{k},\widetilde{G}({\boldsymbol{x}})^{\otimes k}\right\rangle\ (6) for some m\in\mathbb{N} , nonnegative number \lambda_{0} and {(2q)^{k}}\times{(2q)^{k}} positive semidefinite matrices \Lambda_{k} , k=1,\ldots,m (Theorem 20 ). Here, \widetilde{G}({\boldsymbol{x}}) denotes the block-diagonal matrix \diag(G({\boldsymbol{x}}),I_{q}-G({\boldsymbol{x}})) . (iii) Assume that f({\boldsymbol{x}}) and G({\boldsymbol{x}}) exhibits the correlative sparsity–i.e., G({\boldsymbol{x}}) is block-diagonal and {\boldsymbol{x}} can be grouped into overlapping subsets satisfying running intersection property (Assumption 24 ), such that each monomial in f({\boldsymbol{x}}) and each block in G({\boldsymbol{x}}) depend only on one subset–we derive sparse version of the representations ( 5 ) and ( 6 ), that requires much fewer PSD matrices. (iv) Applying the representations ( 5 ) and ( 6 ) to polynomial optimization with PMI constraints, we develop a hierarchy of SDP relaxations and analysis their asymptotic behavior and exactness. As