Non-SOS Positivstellensätze for semi-algebraic sets defined by polynomial matrix inequalities
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916928026574848 |
|---|---|
| author | Guo, Feng |
| author_facet | Guo, Feng |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_01159 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Non-SOS Positivstellensätze for semi-algebraic sets defined by polynomial matrix inequalities Guo, Feng Optimization and Control 90C23, 90C22, 90C26, 14P10, 13J30 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. |
| title | Non-SOS Positivstellensätze for semi-algebraic sets defined by polynomial matrix inequalities |
| topic | Optimization and Control 90C23, 90C22, 90C26, 14P10, 13J30 |
| url | https://arxiv.org/abs/2509.01159 |