Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization

Understand

The abbreviations LMI and SOS stand for `linear matrix inequality' and `sum of squares', respectively.

• The cone $\Sigma_{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 $\binom{n+d}{n}$.
• In other words, $\Sigma_{n,2d}$ is a linear image of a set described by one LMI of size $\binom{n+d}{n}$.
• We show that $\Sigma_{n,2d}$ has no semidefinite extended formulation with finitely many LMIs of size less than $\binom{n+d}{n}$.