Positively not SOS: pseudo-moments and extreme rays in exact arithmetic
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916928195395584 |
|---|---|
| author | Henrion, Didier |
| author_facet | Henrion, Didier |
| contents | A polynomial that is a sum of squares (SOS) of other polynomials is evidently positive. The converse is not true, there are positive polynomials which are not SOS. This note focuses on the problem of certifying, in exact arithmetic, that a given positive polynomial is not SOS. Using convex duality, this can be achieved by constructing a separating linear functional called a pseudo-moment certificate. We present constructive procedures to compute such certificates with rational coefficients for several famous forms (homogeneous polynomials) that are known to be positive but not SOS. Our method leverages polynomial symmetries to reduce the problem size and provides explicit integer-based formulas for generating these rational certificates. As a by-product, we can also generate extreme rays of the pseudomoment cone in exact arithmetic. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_01382 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Positively not SOS: pseudo-moments and extreme rays in exact arithmetic Henrion, Didier Optimization and Control A polynomial that is a sum of squares (SOS) of other polynomials is evidently positive. The converse is not true, there are positive polynomials which are not SOS. This note focuses on the problem of certifying, in exact arithmetic, that a given positive polynomial is not SOS. Using convex duality, this can be achieved by constructing a separating linear functional called a pseudo-moment certificate. We present constructive procedures to compute such certificates with rational coefficients for several famous forms (homogeneous polynomials) that are known to be positive but not SOS. Our method leverages polynomial symmetries to reduce the problem size and provides explicit integer-based formulas for generating these rational certificates. As a by-product, we can also generate extreme rays of the pseudomoment cone in exact arithmetic. |
| title | Positively not SOS: pseudo-moments and extreme rays in exact arithmetic |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2509.01382 |