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

Gennadiy Averkov

Published 2018-06-22Version 1

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}$. Thus, the standard extended formulation of $\Sigma_{n,2d}$ is optimal in terms of the size of the LMIs. As a direct consequence, it follows that the cone of $k \times k$ symmetric positive semidefinite matrices has no extended formulation with finitely many LMIs of size less than $k$. We also derive analogous results further cones considered in polynomial optimization such as truncated quadratic module, the cones of co-positive and completely positive matrices and the cone of sums of non-negative circuit polynomials.