{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T21:43:12Z","timestamp":1771623792330,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,1,25]],"date-time":"2020-01-25T00:00:00Z","timestamp":1579910400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,1,25]],"date-time":"2020-01-25T00:00:00Z","timestamp":1579910400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"European Union\u2019s Horizon 2020 research and innovation programme under the Marie Sk\u0142odowska-Curie grant agreement","award":["764759"],"award-info":[{"award-number":["764759"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,6]]},"abstract":"Abstract<\/jats:title>We consider the problem of computing the minimum value $$f_{\\min ,K}$$<\/jats:tex-math>\n \n f<\/mml:mi>\n \n min<\/mml:mo>\n ,<\/mml:mo>\n K<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of a polynomial f<\/jats:italic> over a compact set $$K\\subseteq {\\mathbb {R}}^n$$<\/jats:tex-math>\n \n K<\/mml:mi>\n \u2286<\/mml:mo>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which can be reformulated as finding a probability measure $$\\nu $$<\/jats:tex-math>\n \u03bd<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> on $$K$$<\/jats:tex-math>\n K<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> minimizing $$\\int _Kf d\\nu $$<\/jats:tex-math>\n \n \n \u222b<\/mml:mo>\n K<\/mml:mi>\n <\/mml:msub>\n f<\/mml:mi>\n d<\/mml:mi>\n \u03bd<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Lasserre showed that it suffices to consider such measures of the form $$\\nu = q\\mu $$<\/jats:tex-math>\n \n \u03bd<\/mml:mi>\n =<\/mml:mo>\n q<\/mml:mi>\n \u03bc<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where q<\/jats:italic> is a sum-of-squares polynomial and $$\\mu $$<\/jats:tex-math>\n \u03bc<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a given Borel measure supported on $$K$$<\/jats:tex-math>\n K<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. By bounding the degree of q<\/jats:italic> by 2r<\/jats:italic> one gets a converging hierarchy of upper bounds $$f^{(r)}$$<\/jats:tex-math>\n \n f<\/mml:mi>\n \n (<\/mml:mo>\n r<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u00a0 for $$f_{\\min ,K}$$<\/jats:tex-math>\n \n f<\/mml:mi>\n \n min<\/mml:mo>\n ,<\/mml:mo>\n K<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. When K<\/jats:italic> is the hypercube $$[-1, 1]^n$$<\/jats:tex-math>\n \n \n [<\/mml:mo>\n -<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, equipped with the Chebyshev measure, the parameters $$f^{(r)}$$<\/jats:tex-math>\n \n f<\/mml:mi>\n \n (<\/mml:mo>\n r<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are known to converge to $$f_{\\min , K}$$<\/jats:tex-math>\n \n f<\/mml:mi>\n \n min<\/mml:mo>\n ,<\/mml:mo>\n K<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> at a rate in $$O(1\/r^2)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n \n r<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We extend this error estimate to a wider class of convex bodies, while also allowing for a broader class of reference measures, including the Lebesgue measure. Our analysis applies to simplices, balls and convex bodies that locally look like a ball. In addition, we show an error estimate in $$O(\\log r \/ r)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n r<\/mml:mi>\n \/<\/mml:mo>\n r<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> when $$K$$<\/jats:tex-math>\n K<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> satisfies a minor geometrical condition, and in $$O(\\log ^2 r \/ r^2)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n log<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:msup>\n r<\/mml:mi>\n \/<\/mml:mo>\n \n r<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> when $$K$$<\/jats:tex-math>\n K<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a convex body, equipped with the Lebesgue measure. This improves upon the currently best known error estimates in $$O(1 \/ \\sqrt{r})$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n \n r<\/mml:mi>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$O(1\/r)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n r<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for these two respective cases.\n<\/jats:p>","DOI":"10.1007\/s10107-020-01468-3","type":"journal-article","created":{"date-parts":[[2020,1,25]],"date-time":"2020-01-25T05:00:50Z","timestamp":1579928450000},"page":"831-871","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Improved convergence analysis of Lasserre\u2019s measure-based upper bounds for polynomial minimization on compact sets"],"prefix":"10.1007","volume":"193","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,1,25]]},"reference":[{"key":"1468_CR1","volume-title":"Theory of Convex Bodies","author":"T Bonnesen","year":"1987","unstructured":"Bonnesen, T., Fenchel, W.: Theory of Convex Bodies. BCS Associates, Mountain View (1987)"},{"key":"1468_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-31256-9","volume-title":"Convex Analysis and Nonlinear Optimization","author":"J Borwein","year":"2006","unstructured":"Borwein, J., Lewis, A.: Convex Analysis and Nonlinear Optimization. Springer, Berlin (2006)"},{"key":"1468_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-6660-4","volume-title":"Approximation Theory and Harmonic Analysis on Spheres and Balls","author":"F Dai","year":"2013","unstructured":"Dai, F., Xu, Y.: Approximation Theory and Harmonic Analysis on Spheres and Balls. Springer, Berlin (2013)"},{"issue":"1","key":"1468_CR4","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1017\/S1446788700014634","volume":"81","author":"L Dalla","year":"2006","unstructured":"Dalla, L., Hatziafratis, T.: Strict convexity of sets in analytic terms. J. Aust. Math. Soc. 81(1), 49\u201361 (2006)","journal-title":"J. Aust. Math. Soc."},{"key":"1468_CR5","first-page":"83","volume":"48","author":"L Dalla","year":"2007","unstructured":"Dalla, L., Samiou, E.: Curvature and q-strict convexity. Beitr. Algebra Geom. 48, 83\u201393 (2007)","journal-title":"Beitr. Algebra Geom."},{"issue":"1\u20132","key":"1468_CR6","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0167-8396(87)90029-X","volume":"4","author":"C de Boor","year":"1987","unstructured":"de Boor, C.: Cutting corners always works. Comput. Aided Geom. Des. 4(1\u20132), 125\u2013131 (1987)","journal-title":"Comput. Aided Geom. Des."},{"key":"1468_CR7","doi-asserted-by":"crossref","unstructured":"de Klerk, E., Kuhn, D., Postek, K.: Distributionally robust optimization with polynomial densities: theory, models and algorithms. Math. Program. (2019). https:\/\/doi.org\/10.1007\/s10107-019-01429-5","DOI":"10.1007\/s10107-019-01429-5"},{"key":"1468_CR8","doi-asserted-by":"publisher","first-page":"1317","DOI":"10.1287\/moor.2017.0906","volume":"43","author":"E de Klerk","year":"2017","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 (2017)","journal-title":"Math. Oper. Res."},{"key":"1468_CR9","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-030-21170-7_1","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, pp. 17\u201356. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-21170-7_1"},{"key":"1468_CR10","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2018.0983","author":"E de Klerk","year":"2019","unstructured":"de Klerk, E., Laurent, M.: Worst-case examples for Lasserre\u2019s measure-based hierarchy for polynomial optimization on the hypercube. Math. Oper. Res. (2019). https:\/\/doi.org\/10.1287\/moor.2018.0983","journal-title":"Math. Oper. Res."},{"key":"1468_CR11","doi-asserted-by":"crossref","unstructured":"de Klerk, E., Laurent, M.: Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere. Math. Program. (2020) (accepted\/in press)","DOI":"10.1007\/s10107-019-01465-1"},{"issue":"1","key":"1468_CR12","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. 162(1), 363\u2013392 (2017)","journal-title":"Math. Program."},{"issue":"4","key":"1468_CR13","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1137\/S1052623401383248","volume":"12","author":"E de Klerk","year":"2002","unstructured":"de Klerk, E., Pasechnik, D.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875\u2013892 (2002)","journal-title":"SIAM J. Optim."},{"issue":"73\u201376","key":"1468_CR14","first-page":"89","volume":"2","author":"G de Rham","year":"1947","unstructured":"de Rham, G.: Un peu de math\u00e9matiques \u00e0 propos d\u2019une courbe plane. Elem. Math. 2(73\u201376), 89\u201397 (1947)","journal-title":"Elem. Math."},{"key":"1468_CR15","unstructured":"Doherty, A.C., Wehner, S.: Convergence of SDP hierarchies for polynomial optimization on the hypersphere. arXiv:1210.5048 (2012)"},{"key":"1468_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107786134","volume-title":"Orthogonal Polynomials of Several Variables, Encyclopedia of Mathematics and Its Applications","author":"CF Dunkl","year":"2014","unstructured":"Dunkl, C.F., Xu, Y.: Orthogonal Polynomials of Several Variables, Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge (2014)"},{"issue":"1","key":"1468_CR17","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1007\/BF01304948","volume":"23","author":"D Koutroufiotis","year":"1972","unstructured":"Koutroufiotis, D.: On Blaschke\u2019s rolling theorems. Arch. Math. 23(1), 655\u2013670 (1972)","journal-title":"Arch. Math."},{"issue":"1","key":"1468_CR18","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 \u201cneedle\u201d polynomials with application to norming sets and cubature formulas. Acta Math. Hung. 147(1), 46\u201372 (2015)","journal-title":"Acta Math. Hung."},{"issue":"1","key":"1468_CR19","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/BF01208908","volume":"8","author":"A Kro\u00f3","year":"1992","unstructured":"Kro\u00f3, A., Swetits, J.J.: On density of interpolation points, a Kadec-type theorem, and Saff\u2019s principle of contamination in Lp-approximation. Constr. Approx. 8(1), 87\u2013103 (1992)","journal-title":"Constr. Approx."},{"key":"1468_CR20","doi-asserted-by":"publisher","first-page":"600","DOI":"10.4153\/CJM-2012-016-x","volume":"65","author":"A Kro\u00f3","year":"2012","unstructured":"Kro\u00f3, A., Lubinsky, D.: Christoffel functions and universality in the bulk for multivariate orthogonal polynomials. Can. J. Math. 65, 600\u2013620 (2012)","journal-title":"Can. J. Math."},{"issue":"3","key":"1468_CR21","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/100806990","volume":"21","author":"JB Lasserre","year":"2010","unstructured":"Lasserre, J.B.: A new look at nonnegativity on closed sets and polynomial optimization. SIAM J. Optim. 21(3), 864\u2013885 (2010)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"1468_CR22","doi-asserted-by":"publisher","first-page":"1439","DOI":"10.1007\/s10444-019-09673-1","volume":"45","author":"JB Lasserre","year":"2019","unstructured":"Lasserre, J.B., Pauwels, E.: The empirical Christoffel function with applications in data analysis. Adv. Comput. Math. 45(3), 1439\u20131468 (2019)","journal-title":"Adv. Comput. Math."},{"key":"1468_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-019-01416-x","author":"A Martinez","year":"2019","unstructured":"Martinez, A., Piazzon, F., Sommariva, A., Vianello, M.: Quadrature-based polynomial optimization. Optim. Lett. (2019). https:\/\/doi.org\/10.1007\/s11590-019-01416-x","journal-title":"Optim. Lett."},{"key":"1468_CR24","doi-asserted-by":"publisher","first-page":"533","DOI":"10.4153\/CJM-1965-053-6","volume":"17","author":"TS Motzkin","year":"1965","unstructured":"Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Tur\u00e1n. Can. J. Math. 17, 533\u2013540 (1965)","journal-title":"Can. J. Math."},{"key":"1468_CR25","volume-title":"The Chebyshev Polynomials","author":"TJ Rivlin","year":"1990","unstructured":"Rivlin, T.J.: The Chebyshev Polynomials. Wiley-Interscience, New York (1990)"},{"key":"1468_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-0673-0","volume-title":"Hausdorff Approximations","author":"B Sendov","year":"1990","unstructured":"Sendov, B.: Hausdorff Approximations. Kluwer Academic Publishers, Dordrecht (1990)"},{"key":"1468_CR27","first-page":"233","volume-title":"Twelve Proofs of the Markov Inequality. Approximation Theory\u2014A Volume Dedicated to B. Bojanov","author":"A Shadrin","year":"2004","unstructured":"Shadrin, A.: Twelve Proofs of the Markov Inequality. Approximation Theory\u2014A Volume Dedicated to B. Bojanov, pp. 233\u2013298. Professor Marin Drinov Publishing House, Sofia (2004)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01468-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01468-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01468-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T14:26:08Z","timestamp":1654871168000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01468-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,25]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["1468"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01468-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,25]]},"assertion":[{"value":"20 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}