EUVIMEDEUVIMED entdecken
Crossref

Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization

Gennadiy Averkov

SIAM Journal on Applied Algebra and Geometry · 2019-01 · 3 (1) · 128-151

DOI: 10.1137/18m1201342 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Applied Algebra and Geometry, online erschienen am 14.03.2019. Verfasst von Gennadiy Averkov. Die Arbeit wurde bisher 30-mal zitiert (Crossref) und nennt 41 Literaturangaben. Gefördert von: Deutsche Forschungsgemeinschaft.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 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.

Förderung

  • Deutsche Forschungsgemeinschaft

Zitieren

APA

Averkov, G. (2019). Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization. SIAM Journal on Applied Algebra and Geometry, 3(1), 128-151. https://doi.org/10.1137/18m1201342

Vancouver

Averkov G. Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization. SIAM Journal on Applied Algebra and Geometry. 2019;3(1):128-151. doi:10.1137/18m1201342

BibTeX
@article{Averkov2019,
  author = {Averkov, Gennadiy},
  title = {Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization},
  journal = {SIAM Journal on Applied Algebra and Geometry},
  year = {2019},
  volume = {3},
  number = {1},
  pages = {128--151},
  doi = {10.1137/18m1201342}
}
Kostenlos starten →