Non-SOS Positivstellensätze for Semialgebraic Sets Defined by Polynomial Matrix Inequalities

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 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. Funding: F. Guo was supported by the National Natural Science Foundation [Grant 12471478].