Non-SOS Positivstellensa¨tze for Semialgebraic Sets Defined by Polynomial Matrix Inequalities

• 成果类型: Article; Early Access
• 署名作者: Guo, Feng
• 署名单位: Dalian University of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2025.1239
• 发表日期: 2026-06-08
• 关键词: Positivstellensa & uml; tze; polynomial matrix inequality; Handelman Positivstellensatz; Krivine-Stengle Positivstellensatz; correlative sparsity; semidefinite optimization; polynomial optimization; LP-RELAXATIONS; squares; optimization; sums

摘要

This paper establishes new Positivstellensa & uml;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 of the direct sum of the matrix and the identity minus it) 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 optimization relaxations in which the size of the positive semidefinite matrices 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 numbers of variables and low-dimensional matrix constraints, offering a practical alternative where the SOS-based relaxations become intractable.