{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T13:26:28Z","timestamp":1787232388495,"version":"3.56.0"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["314838170, GRK 2297 MathCoRe"],"award-info":[{"award-number":["314838170, GRK 2297 MathCoRe"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Appl. Algebra Geometry"],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>The abbreviations LMI and SOS stand for \u201clinear matrix inequality\" and \u201csum 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.<\/jats:p>","DOI":"10.1137\/18m1201342","type":"journal-article","created":{"date-parts":[[2019,3,14]],"date-time":"2019-03-14T11:55:04Z","timestamp":1552564504000},"page":"128-151","source":"Crossref","is-referenced-by-count":28,"title":["Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization"],"prefix":"10.1137","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2245-9958","authenticated-orcid":true,"given":"Gennadiy","family":"Averkov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,3,14]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"A. A. Ahmadi, G. Hall, A. Papachristodoulou, J. Saunderson, and Y. Zheng,\n                      Improving efficiency and scalability of sum of squares optimization: Recent advances and limitations\n                      , in Proceedings of the 56th Annual IEEE Conference on Decision and Control (CDC), 2017, pp. 453-462.","DOI":"10.1109\/CDC.2017.8263706"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"M. F. Anjos and J. B. Lasserre, eds.\n                      Handbook on Semidefinite, Conic and Polynomial Optimization\n                      , Internat. Ser. Oper. Res. Management Sci. 166, Springer, New York, 2012,https:\/\/doi.org\/10.1007\/978-1-4614-0769-0.","DOI":"10.1007\/978-1-4614-0769-0_1"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1134-7"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"A. Ben-Tal and A. Nemirovski,\n                      Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications\n                      , MPS\/SIAM Ser. Optim. 2, SIAM, Philadelphia; MPS, Philadelphia, 2001,https:\/\/doi.org\/10.1137\/1.9780898718829.","DOI":"10.1137\/1.9780898718829"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/140988978"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-0998-2"},{"key":"atypb7","unstructured":"T. de Wolff,\n                      private communication\n                      , 2018."},{"key":"atypb8","unstructured":"M. Dressler,\n                      Sums of Nonnegative Circuit Polynomials\n                      , Ph.D. thesis, Goethe-Universit\u00e4t Frankfurt am Main, Frankfurt, Germany, 2018."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/16M1086303"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2018.06.018"},{"key":"atypb11","unstructured":"R. J. Duffin, E. L. Peterson, and C. Zener,\n                      Geometric Programming: Theory and Application\n                      , John Wiley & Sons, New York, London, Sydney, 1967."},{"key":"atypb12","first-page":"3","author":"D\u00fcr M.","year":"2010","journal-title":"Heidelberg"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"H. Fawzi,\n                      On representing the positive semidefinite cone using the second-order cone\n                      , Math. Program. (2018),https:\/\/doi.org\/10.1007\/s10107-018-1233-0.","DOI":"10.1007\/s10107-018-1233-0"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0922-1"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/17M1142570"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/140966265"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0977-z"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0813"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2012.09.015"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s00013-010-0179-0"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/110836869"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/16M1105608"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0575"},{"key":"atypb24","unstructured":"R. L. Graham, B. L. Rothschild, and J. H. Spencer,\n                      Ramsey Theory\n                      , 2nd ed., Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley & Sons, New York, 1990."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/BF01443605"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1186\/s40687-016-0052-2"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"J. B. Lasserre,\n                      An Introduction to Polynomial and Semi-Algebraic Optimization\n                      , Cambridge Texts Appl. Math., Cambridge University Press, Cambridge, UK, 2015,https:\/\/doi.org\/10.1017\/CBO9781107447226.","DOI":"10.1017\/CBO9781107447226"},{"key":"atypb28","first-page":"157","author":"Laurent M.","year":"2009","journal-title":"New York"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"J. R. Lee, P. Raghavendra, and D. Steurer,\n                      Lower bounds on the size of semidefinite programming relaxations\n                      , in Proceedings of the ACM Symposium on Theory of Computing (STOC), 2015, pp. 567-576.","DOI":"10.1145\/2746539.2746599"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"M. Marshall,\n                      Positive Polynomials and Sums of Squares\n                      , Math. Surveys Monogr. 146, American Mathematical Society, Providence, RI, 2008,https:\/\/doi.org\/10.1090\/surv\/146.","DOI":"10.1090\/surv\/146"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1017\/S0013091500014681"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0355-5"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0797-6"},{"key":"atypb34","unstructured":"R. T. Rockafellar,\n                      Convex Analysis\n                      , Princeton Landmarks Math., Princeton University Press, Princeton, NJ, 1997."},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0804-y"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/14096339X"},{"key":"atypb37","unstructured":"J. F. Saunderson,\n                      Semidefinite Representations with Applications in Estimation and Inference\n                      , Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, 2015; available online fromhttp:\/\/gateway.proquest.com\/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi\/fmt:kev:mtx:dissertation&res_dat=xri:pqm&rft_dat=xri:pqdiss:0831101."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/17M1118981"},{"key":"atypb39","unstructured":"H. Seidler and T. de Wolff,\n                      An Experimental Comparison of SONC and SOS Certificates for Unconstrained Optimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1808.08431, 2018."},{"key":"atypb40","doi-asserted-by":"crossref","unstructured":"H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds.\n                      Handbook of Semidefinite Programming. Theory, Algorithms, and Applications\n                      , Internat. Ser. Oper. Res. Management Sci. 27, Kluwer Academic Publishers, Boston, MA, 2000,https:\/\/doi.org\/10.1007\/978-1-4615-4381-7.","DOI":"10.1007\/978-1-4615-4381-7"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"G. M. Ziegler,\n                      Lectures on Polytopes\n                      , Grad. Texts in Math. 152, Springer-Verlag, New York, 1995,https:\/\/doi.org\/10.1007\/978-1-4613-8431-1.","DOI":"10.1007\/978-1-4613-8431-1"}],"container-title":["SIAM Journal on Applied Algebra and Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1201342","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T12:45:02Z","timestamp":1787229902000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1201342"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/18M1201342"],"URL":"https:\/\/doi.org\/10.1137\/18m1201342","relation":{},"ISSN":["2470-6566"],"issn-type":[{"value":"2470-6566","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}