{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T22:56:33Z","timestamp":1768172193632,"version":"3.49.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,10,30]],"date-time":"2020-10-30T00:00:00Z","timestamp":1604016000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,10,30]],"date-time":"2020-10-30T00:00:00Z","timestamp":1604016000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100011264","name":"FP7 People: Marie-Curie Actions","doi-asserted-by":"publisher","award":["764759 (MINOA)"],"award-info":[{"award-number":["764759 (MINOA)"]}],"id":[{"id":"10.13039\/100011264","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider a hierarchy of upper approximations for the minimization of a polynomial <jats:italic>f<\/jats:italic> over a compact set <jats:inline-formula><jats:alternatives><jats:tex-math>$$K \\subseteq \\mathbb {R}^n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>K<\/mml:mi>\n                    <mml:mo>\u2286<\/mml:mo>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mi>R<\/mml:mi>\n                      <\/mml:mrow>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> proposed recently by Lasserre (arXiv:1907.097784, 2019). This hierarchy relies on using the push-forward measure of the Lebesgue measure on <jats:italic>K<\/jats:italic> by the polynomial <jats:italic>f<\/jats:italic> and involves univariate sums of squares of polynomials with growing degrees 2<jats:italic>r<\/jats:italic>. Hence it is weaker, but cheaper to compute, than an earlier hierarchy by Lasserre (SIAM Journal on Optimization 21(3), 864\u2013885, 2011), which uses multivariate sums of squares. We show that this new hierarchy converges to the global minimum of <jats:italic>f<\/jats:italic> at a rate in <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\log ^2 r \/ r^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mo>log<\/mml:mo>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mi>r<\/mml:mi>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>r<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> whenever <jats:italic>K<\/jats:italic> satisfies a mild geometric condition, which holds, eg., for convex bodies and for compact semialgebraic sets with dense interior. As an application this rate of convergence also applies to the stronger hierarchy based on multivariate sums of squares, which improves and extends earlier convergence results to a wider class of compact sets. Furthermore, we show that our analysis is near-optimal by proving a lower bound on the convergence rate in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varOmega (1\/r^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>r<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for a class of polynomials on <jats:inline-formula><jats:alternatives><jats:tex-math>$$K=[-1,1]$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>K<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mo>[<\/mml:mo>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>]<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, obtained by exploiting a connection to orthogonal polynomials.<\/jats:p>","DOI":"10.1007\/s10107-020-01586-y","type":"journal-article","created":{"date-parts":[[2020,10,30]],"date-time":"2020-10-30T06:02:41Z","timestamp":1604037761000},"page":"443-460","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Near-optimal analysis of Lasserre\u2019s univariate measure-based bounds for multivariate polynomial optimization"],"prefix":"10.1007","volume":"188","author":[{"given":"Lucas","family":"Slot","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8474-2121","authenticated-orcid":false,"given":"Monique","family":"Laurent","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,10,30]]},"reference":[{"issue":"2\u20133","key":"1586_CR1","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1016\/j.tcs.2006.05.011","volume":"361","author":"E de Klerk","year":"2006","unstructured":"de Klerk, E., Laurent, M., Parrilo, P.: A PTAS for the minimization of polynomials of fixeddegree over the simplex. Theor. Comput. Sci. 361(2\u20133), 210\u2013225 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"1586_CR2","doi-asserted-by":"publisher","first-page":"3104","DOI":"10.1137\/100790835","volume":"20","author":"E de Klerk","year":"2010","unstructured":"de Klerk, E., Laurent, M.: Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube. SIAM J. Optim. 20(6), 3104\u20133120 (2010)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1586_CR3","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s10107-016-1043-1","volume":"162","author":"E de Klerk","year":"2017","unstructured":"de Klerk, E., Laurent, M., Sun, Z.: Convergence analysis for Lasserre\u2019s measure-based hierarchy of upper bounds for polynomial optimization. Math. Program. Ser. A 162(1), 363\u2013392 (2017)","journal-title":"Math. Program. Ser. A"},{"key":"1586_CR4","doi-asserted-by":"publisher","first-page":"1317","DOI":"10.1287\/moor.2017.0906","volume":"43","author":"E de Klerk","year":"2018","unstructured":"de Klerk, E., Laurent, M.: Comparison of Lasserre\u2019s measure-based bounds for polynomial optimization to bounds obtained by simulated annealing. Math. Oper. Res. 43, 1317\u20131325 (2018)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1586_CR5","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1287\/moor.2018.0983","volume":"45","author":"E de Klerk","year":"2020","unstructured":"de Klerk, E., Laurent, M.: Worst-case examples for Lasserre\u2019s measure-based hierarchy for polynomial optimization on the hypercube. Math. Oper. Res. 45(1), 86\u201398 (2020)","journal-title":"Math. Oper. Res."},{"key":"1586_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01465-1","author":"E de Klerk","year":"2020","unstructured":"de Klerk, E., Laurent, M.: Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere. Math. Program. (2020). https:\/\/doi.org\/10.1007\/s10107-019-01465-1","journal-title":"Math. Program."},{"key":"1586_CR7","volume-title":"World Women in Mathematics 2018. Association for Women in Mathematics Series","author":"E de Klerk","year":"2019","unstructured":"de Klerk, E., Laurent, M.: A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis. In: Araujo, C., Benkart, G., Praeger, C., Tanbay, B. (eds.) World Women in Mathematics 2018. Association for Women in Mathematics Series, vol. 20. Springer, Cham (2019)"},{"key":"1586_CR8","doi-asserted-by":"publisher","first-page":"1793","DOI":"10.1016\/j.jat.2009.11.006","volume":"162","author":"DK Dimitrov","year":"2010","unstructured":"Dimitrov, D.K., Nikolov, G.P.: Sharp bounds for the extreme zeros of classical orthogonal polynomials. J. Approx. Theory 162, 1793\u20131804 (2010)","journal-title":"J. Approx. Theory"},{"key":"1586_CR9","unstructured":"Doherty, A.C., Wehner, S.: Convergence of SDP hierarchies for polynomial optimization on the hypersphere (2013). arXiv:1210.5048v2"},{"key":"1586_CR10","doi-asserted-by":"publisher","first-page":"1200","DOI":"10.1016\/j.jat.2012.05.014","volume":"164","author":"K Driver","year":"2012","unstructured":"Driver, K., Jordaan, K.: Bounds for extreme zeros of some classical orthogonal polynomials. J. Approx. Theory 164, 1200\u20131204 (2012)","journal-title":"J. Approx. Theory"},{"key":"1586_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01537-7","author":"K Fang","year":"2020","unstructured":"Fang, K., Fawzi, H.: The sum-of-squares hierarchy on the sphere and applications in quantum information theory. Math. Program. (2020). https:\/\/doi.org\/10.1007\/s10107-020-01537-7","journal-title":"Math. Program."},{"issue":"1","key":"1586_CR12","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/s10474-015-0507-8","volume":"147","author":"A Kro\u00f3","year":"2015","unstructured":"Kro\u00f3, A.: Multivariate needle polynomials with application to norming sets and cubature formulas. Acta Math. Hung. 147(1), 46\u201372 (2015)","journal-title":"Acta Math. Hung."},{"key":"1586_CR13","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796\u2013817 (2001)","journal-title":"SIAM J. Optim."},{"key":"1586_CR14","doi-asserted-by":"publisher","DOI":"10.1142\/p665","volume-title":"Moments, Positive Polynomials and Their Applications","author":"JB Lasserre","year":"2009","unstructured":"Lasserre, J.B.: Moments, Positive Polynomials and Their Applications. Imperial College Press, London (2009)"},{"issue":"3","key":"1586_CR15","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/100806990","volume":"21","author":"J-B Lasserre","year":"2011","unstructured":"Lasserre, J.-B.: A new look at nonnegativity on closed sets and polynomial optimization. SIAM J. Optim. 21(3), 864\u2013885 (2011)","journal-title":"SIAM J. Optim."},{"key":"1586_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107447226","volume-title":"An Introduction to Polynomial and Semi-algebraic Optimization (Cambridge Texts in Applied Mathematics)","author":"J-B Lasserre","year":"2015","unstructured":"Lasserre, J.-B.: An Introduction to Polynomial and Semi-algebraic Optimization (Cambridge Texts in Applied Mathematics). Cambridge University Press, Cambridge (2015)"},{"key":"1586_CR17","doi-asserted-by":"crossref","unstructured":"Lasserre, J.B.: Connecting optimization with spectral analysis of tri-diagonal Hankel matrices (2019). arXiv:1907.097784","DOI":"10.1007\/s10107-020-01549-3"},{"key":"1586_CR18","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.jco.2006.07.002","volume":"23","author":"J Nie","year":"2007","unstructured":"Nie, J., Schweighofer, M.: On the complexity of Putinar\u2019s Positivstellensatz. J. Complex. 23, 135\u2013150 (2007)","journal-title":"J. Complex."},{"key":"1586_CR19","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF01458617","volume":"275","author":"W Paw\u0142ucki","year":"1986","unstructured":"Paw\u0142ucki, W., Ple\u015bniak, W.: Markov\u2019s inequality and C$$^\\infty $$ functions on sets with polynomial cusps. Math. Ann. 275, 467\u2013480 (1986)","journal-title":"Math. Ann."},{"key":"1586_CR20","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. Ind. Univ. Math. J. 42, 969\u2013984 (1993)","journal-title":"Ind. Univ. Math. J."},{"key":"1586_CR21","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/BF01446568","volume":"289","author":"K Schm\u00fcdgen","year":"1991","unstructured":"Schm\u00fcdgen, K.: The $$K$$-moment problem for compact semi-algebraic sets. Math. Ann. 289, 203\u2013206 (1991)","journal-title":"Math. Ann."},{"issue":"4","key":"1586_CR22","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1016\/j.jco.2004.01.005","volume":"20","author":"M Schweighofer","year":"2004","unstructured":"Schweighofer, M.: On the complexity of Schm\u00fcdgen?s Positivstellensatz. J. Complex. 20(4), 529\u2013543 (2004)","journal-title":"J. Complex."},{"key":"1586_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01468-3","author":"L Slot","year":"2020","unstructured":"Slot, L., Laurent, M.: Improved convergence analysis of Lasserre\u2019s measure-based upper bounds for polynomial minimization on compact sets. Math. Program. (2020). https:\/\/doi.org\/10.1007\/s10107-020-01468-3","journal-title":"Math. Program."},{"key":"1586_CR24","volume-title":"Orthogonal Polynomials","author":"G Szeg\u00f6","year":"1975","unstructured":"Szeg\u00f6, G.: Orthogonal Polynomials. American Mathematical Society Colloquium Publications, Providence (1975)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01586-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01586-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01586-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,16]],"date-time":"2021-07-16T13:15:50Z","timestamp":1626441350000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01586-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,30]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["1586"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01586-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,30]]},"assertion":[{"value":"30 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 October 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}