Answers are grounded in this paper and cite their sources.
The abbreviations LMI and SOS stand for “linear matrix inequality" and “sum of squares," respectively. The cone Σn,2d of SOS polynomials in n variables of degree at most $2d$ is known to have a semidefinite extended formulation with one LMI of size n+dn. In other words, Σn,2d is a linear image of a set described by one LMI of size n+dn. We show that Σn,2d has no semidefinite extended formulation with finitely many LMIs of size less than n+dn. Thus, the standard extended formulation of Σn,2d is optimal in terms of the size of the LMIs. As a direct consequence, it follows that the cone of k× k symmetric positive semidefinite matrices has no extended formulation with finitely many LMIs of size less than k. We also derive analogous results for further cones considered in polynomial optimization, such as truncated quadratic modules, the cones of copositive and completely positive matrices, and the cone of sums of nonnegative circuit polynomials.
No takes yet. Share an insight, caveat, or question.
Gennadiy Averkov (2019) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: