{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T04:27:50Z","timestamp":1780633670954,"version":"3.54.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,2,16]],"date-time":"2024-02-16T00:00:00Z","timestamp":1708041600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,2,16]],"date-time":"2024-02-16T00:00:00Z","timestamp":1708041600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Brandenburgische TU Cottbus-Senftenberg"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,1]]},"abstract":"Abstract<\/jats:title>\n Consider the closed convex hull K<\/jats:italic> of a monomial curve given parametrically as \n \n $$(t^{m_1},\\ldots ,t^{m_n})$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n \n t<\/mml:mi>\n \n m<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:msup>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n \n t<\/mml:mi>\n \n m<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, with the parameter t<\/jats:italic> varying in an interval I<\/jats:italic>. We show, using constructive arguments, that K<\/jats:italic> admits a lifted semidefinite description by \n \n $$\\mathcal {O}(d)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n d<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> linear matrix inequalities (LMIs), each of size \n \n $$\\left\\lfloor \\frac{n}{2} \\right\\rfloor +1$$<\/jats:tex-math>\n \n \n \n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:mfenced>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, where \n \n $$d= \\max \\{m_1,\\ldots ,m_n\\}$$<\/jats:tex-math>\n \n \n d<\/mml:mi>\n =<\/mml:mo>\n max<\/mml:mo>\n {<\/mml:mo>\n \n m<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n \n m<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is the degree of the curve. On the dual side, we show that if a univariate polynomial p<\/jats:italic>(t<\/jats:italic>) of degree d<\/jats:italic> with at most \n \n $$2k+1$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n k<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> monomials is non-negative on \n \n $${\\mathbb {R}}_+$$<\/jats:tex-math>\n \n \n R<\/mml:mi>\n +<\/mml:mo>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, then p<\/jats:italic> admits a representation \n \n $$p = t^0 \\sigma _0 + \\cdots + t^{d-k} \\sigma _{d-k}$$<\/jats:tex-math>\n \n \n p<\/mml:mi>\n =<\/mml:mo>\n \n t<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msup>\n \n \u03c3<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msub>\n +<\/mml:mo>\n \u22ef<\/mml:mo>\n +<\/mml:mo>\n \n t<\/mml:mi>\n \n d<\/mml:mi>\n -<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n \n \u03c3<\/mml:mi>\n \n d<\/mml:mi>\n -<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, where the polynomials \n \n $$\\sigma _0,\\ldots ,\\sigma _{d-k}$$<\/jats:tex-math>\n \n \n \n \u03c3<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n \n \u03c3<\/mml:mi>\n \n d<\/mml:mi>\n -<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> are sums of squares and \n \n $$\\deg (\\sigma _i) \\le 2k$$<\/jats:tex-math>\n \n \n deg<\/mml:mo>\n (<\/mml:mo>\n \n \u03c3<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n \u2264<\/mml:mo>\n 2<\/mml:mn>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. The latter is a univariate positivstellensatz for sparse polynomials, with non-negativity of p<\/jats:italic> being certified by sos polynomials whose degree only depends on the sparsity of\u00a0p<\/jats:italic>. Our results fit into the general attempt of formulating polynomial optimization problems as semidefinite problems with LMIs of small size. Such small-size descriptions are much more tractable from a computational viewpoint.<\/jats:p>","DOI":"10.1007\/s10107-024-02060-9","type":"journal-article","created":{"date-parts":[[2024,2,16]],"date-time":"2024-02-16T16:02:41Z","timestamp":1708099361000},"page":"113-131","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Convex hulls of monomial curves, and a sparse positivstellensatz"],"prefix":"10.1007","volume":"209","author":[{"given":"Gennadiy","family":"Averkov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Claus","family":"Scheiderer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,2,16]]},"reference":[{"key":"2060_CR1","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/18M118935X","volume":"3","author":"AA Ahmadi","year":"2019","unstructured":"Ahmadi, A.A., Majumdar, A.: DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization. SIAM J. Appl. Algebra Geom. 3, 193\u2013230 (2019)","journal-title":"SIAM J. Appl. Algebra Geom."},{"key":"2060_CR2","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0024-3795(88)90240-6","volume":"107","author":"J Agler","year":"1988","unstructured":"Agler, J., Helton, W., McCullough, S., Rodman, L.: Positive semidefinite matrices with a given sparsity pattern. Linear Algebra Appl. 107, 101\u2013149 (1988)","journal-title":"Linear Algebra Appl."},{"key":"2060_CR3","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1137\/0805002","volume":"5","author":"F Alizadeh","year":"1995","unstructured":"Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5, 13\u201351 (1995)","journal-title":"SIAM J. Optim."},{"key":"2060_CR4","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1137\/18M1201342","volume":"3","author":"G Averkov","year":"2019","unstructured":"Averkov, G.: Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization. SIAM J. Appl. Algebra Geom. 3, 128\u2013151 (2019)","journal-title":"SIAM J. Appl. Algebra Geom."},{"key":"2060_CR5","unstructured":"Averkov, G., Peters, B., Sager, S.: Convexification of polynomial optimization problems by means of monomial patterns. Preprint, arXiv:1901.05675"},{"key":"2060_CR6","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718829","volume-title":"Lectures on Modern Convex Optimization. Analysis, Algorithms, and Engineering Applications","author":"A Ben-Tal","year":"2001","unstructured":"Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization. Analysis, Algorithms, and Engineering Applications. SIAM, MPS, Philadelphia (2001)"},{"key":"2060_CR7","volume-title":"Semidefinite Optimization and Convex Algebraic Geometry","year":"2013","unstructured":"Blekherman, G., Parrilo, P.A., Thomas, R.R. (eds.): Semidefinite Optimization and Convex Algebraic Geometry. SIAM, MOS, Philadelphia (2013)"},{"key":"2060_CR8","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1137\/16M1086303","volume":"1","author":"M Dressler","year":"2017","unstructured":"Dressler, M., Iliman, S., de Wolff, T.: A positivstellensatz for sums of nonnegative circuit polynomials. SIAM J. Appl. Algebra Geom. 1, 536\u2013555 (2017)","journal-title":"SIAM J. Appl. Algebra Geom."},{"key":"2060_CR9","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s10107-018-1233-0","volume":"175","author":"H Fawzi","year":"2019","unstructured":"Fawzi, H.: On representing the positive semidefinite cone using the second-order cone. Math. Program. 175, 109\u2013118 (2019)","journal-title":"Math. Program."},{"key":"2060_CR10","doi-asserted-by":"publisher","first-page":"1297","DOI":"10.1090\/mcom\/3607","volume":"90","author":"L Katth\u00e4n","year":"2021","unstructured":"Katth\u00e4n, L., Naumann, H., Theobald, T.: A unified framework of SAGE and SONC polynomials and its duality theory. Math. Comput. 90, 1297\u20131322 (2021)","journal-title":"Math. Comput."},{"key":"2060_CR11","series-title":"Interscience","volume-title":"Tchebycheff Systems: With Applications in Analysis and Statistics","author":"S Karlin","year":"1966","unstructured":"Karlin, S., Studden, W.J.: Tchebycheff Systems: With Applications in Analysis and Statistics. Interscience, Wiley, New York (1966)"},{"key":"2060_CR12","series-title":"Universitext","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-09800-0","volume-title":"Real Algebra. A First Course","author":"M Knebusch","year":"2022","unstructured":"Knebusch, M., Scheiderer, C.: Real Algebra. A First Course. Universitext, Springer, Berlin (2022)"},{"key":"2060_CR13","doi-asserted-by":"crossref","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11 796\u2013817 (2000\/01)","DOI":"10.1137\/S1052623400366802"},{"key":"2060_CR14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107447226","volume-title":"An Introduction to Polynomial and Semi-algebraic Optimization","author":"JB Lasserre","year":"2015","unstructured":"Lasserre, J.B.: An Introduction to Polynomial and Semi-algebraic Optimization. Cambridge University Press, Cambridge (2015)"},{"key":"2060_CR15","doi-asserted-by":"publisher","first-page":"1703","DOI":"10.1007\/s10208-021-09497-w","volume":"21","author":"R Murray","year":"2021","unstructured":"Murray, R., Chandrasekaran, V., Wierman, A.: Newton polytopes and relative entropy optimization. Found. Comput. Math. 21, 1703\u20131737 (2021)","journal-title":"Found. Comput. Math."},{"key":"2060_CR16","volume-title":"Interior-point Polynomial Algorithms in Convex Programming. SIAM Studies in Applied Mathematics 13","author":"Y Nesterov","year":"1994","unstructured":"Nesterov, Y., Nemirovskii, A.: Interior-point Polynomial Algorithms in Convex Programming. SIAM Studies in Applied Mathematics 13. SIAM, Philadelphia (1994)"},{"key":"2060_CR17","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1512\/iumj.1993.42.42045","volume":"42","author":"M Putinar","year":"1993","unstructured":"Putinar, M.: Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42, 969\u2013984 (1993)","journal-title":"Indiana Univ. Math. J."},{"key":"2060_CR18","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/s10013-022-00548-5","volume":"50","author":"Z Rosen","year":"2022","unstructured":"Rosen, Z., Scholten, G., Vinzant, C.: Sparse moments of univariate step functions and allele frequency spectra. Vietnam J. Math. 50, 523\u2013544 (2022)","journal-title":"Vietnam J. Math."},{"key":"2060_CR19","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1137\/20M133717X","volume":"5","author":"C Scheiderer","year":"2021","unstructured":"Scheiderer, C.: Second-order cone representation for convex sets in the plane. SIAM J. Appl. Algebra Geom. 5, 114\u2013139 (2021)","journal-title":"SIAM J. Appl. Algebra Geom."},{"key":"2060_CR20","unstructured":"Scheiderer, C.: Work in progress (2023)"},{"key":"2060_CR21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511609589","volume-title":"Enumerative Combinatorics, Volume 2 Cambridge Studies in Advanced Mathematics","author":"R Stanley","year":"1999","unstructured":"Stanley, R.: Enumerative Combinatorics, Volume 2 Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge (1999)"},{"key":"2060_CR22","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1561\/2400000006","volume":"1","author":"L Vandenberghe","year":"2015","unstructured":"Vandenberghe, L., Andersen, M.S.: Chordal graphs and semidefinite optimization. Found. Trends Optim. 1, 241\u2013433 (2015)","journal-title":"Found. Trends Optim."},{"key":"2060_CR23","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/19M1307871","volume":"31","author":"J Wang","year":"2021","unstructured":"Wang, J., Magron, V., Lasserre, J.B.: TSSOS: A moment-SOS hierarchy that exploits term sparsity. SIAM J. Optim. 31, 30\u201358 (2021)","journal-title":"SIAM J. Optim."},{"key":"2060_CR24","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1137\/20M1323564","volume":"31","author":"J Wang","year":"2021","unstructured":"Wang, J., Magron, V., Lasserre, J.B.: Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension. SIAM J. Optim. 31, 114\u2013141 (2021)","journal-title":"SIAM J. Optim."},{"key":"2060_CR25","doi-asserted-by":"crossref","unstructured":"Zheng Y., Fantuzzi, G., Papachristodoulou, A., Wynn, A.: Fast ADMM for semidefinite programs with chordal sparsity. In: 2017 American Control Conference (ACC), pp. 3335\u20133340. IEEE","DOI":"10.23919\/ACC.2017.7963462"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02060-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02060-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02060-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T16:51:55Z","timestamp":1736959915000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02060-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,16]]},"references-count":25,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["2060"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02060-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,16]]},"assertion":[{"value":"7 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 February 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}