{
  "id": "1806.08656",
  "version": "v1",
  "published": "2018-06-22T13:36:55.000Z",
  "updated": "2018-06-22T13:36:55.000Z",
  "title": "Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization",
  "authors": [
    "Gennadiy Averkov"
  ],
  "categories": [
    "math.OC",
    "math.AG",
    "math.CO",
    "math.MG"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-06-22T13:36:55.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "linear matrix inequality",
      "polynomial optimization",
      "semidefinite approaches",
      "optimal size",
      "semidefinite extended formulation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}