{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T10:39:00Z","timestamp":1778755140311,"version":"3.51.4"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,1,21]],"date-time":"2020-01-21T00:00:00Z","timestamp":1579564800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,1,21]],"date-time":"2020-01-21T00:00:00Z","timestamp":1579564800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007659","name":"Tilburg University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the convergence rate of a hierarchy of upper bounds for polynomial minimization problems, proposed by Lasserre (SIAM J Optim 21(3):864\u2013885, 2011), for the special case when the feasible set is the unit (hyper)sphere. The upper bound at level <jats:inline-formula><jats:alternatives><jats:tex-math>$$r \\in {\\mathbb {N}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>r<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mi>N<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of the hierarchy is defined as the minimal expected value of the polynomial over all probability distributions on the sphere, when the probability density function is a sum-of-squares polynomial of degree at most 2<jats:italic>r<\/jats:italic> with respect to the surface measure. We show that the rate of convergence is <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(1\/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: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> and we give a class of polynomials of any positive degree for which this rate is tight. In addition, we explore the implications for the related rate of convergence for the generalized problem of moments on the sphere.<\/jats:p>","DOI":"10.1007\/s10107-019-01465-1","type":"journal-article","created":{"date-parts":[[2020,1,21]],"date-time":"2020-01-21T14:03:41Z","timestamp":1579615421000},"page":"665-685","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":24,"title":["Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere"],"prefix":"10.1007","volume":"193","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3377-0063","authenticated-orcid":false,"given":"Etienne","family":"de Klerk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Monique","family":"Laurent","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,1,21]]},"reference":[{"issue":"1\u20132","key":"1465_CR1","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s10107-011-0499-2","volume":"137","author":"AA Ahmadi","year":"2013","unstructured":"Ahmadi, A.A., Olshevsky, A., Parrilo, P.A., Tsitsiklis, J.N.: NP-hardness of deciding convexity of quartic polynomials and related problems. Math. Program. 137(1\u20132), 453\u2013476 (2013)","journal-title":"Math. Program."},{"key":"1465_CR2","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, New York (2013)"},{"key":"1465_CR3","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":"1465_CR4","unstructured":"Doherty, A.C., Wehner, S.: Convergence of SDP hierarchies for polynomial optimization on the hypersphere. arXiv:1210.5048v2 (2013)"},{"key":"1465_CR5","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":"1465_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511565717","volume-title":"Orthogonal Polynomials of Several Variables. Encyclopedia of Mathematics","author":"CF Dunkl","year":"2001","unstructured":"Dunkl, C.F., Xu, Y.: Orthogonal Polynomials of Several Variables. Encyclopedia of Mathematics. Cambridge University Press, Cambridge (2001)"},{"key":"1465_CR7","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."},{"key":"1465_CR8","unstructured":"De Klerk, E., Laurent, M.: Worst-case examples for Lasserre\u2019s measure-based hierarchy for polynomial optimization on the hypercube. To appear in Math. Oper. Res. arXiv:1804.05524 (2018)"},{"key":"1465_CR9","doi-asserted-by":"crossref","unstructured":"De Klerk, E., Laurent, M.: A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis. To appear in World Women Math. 2018 (Association for Women in Mathematics Series 20, Springer). arXiv:1811.05439 (2018)","DOI":"10.1007\/978-3-030-21170-7_1"},{"key":"1465_CR10","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/10997703_7","volume-title":"Positive Polynomials in Control","author":"E De Klerk","year":"2005","unstructured":"De Klerk, E., Laurent, M., Parrilo, P.A.: On the equivalence of algebraic approaches to the minimization of forms on the simplex. In: Henrion, D., Garulli, A. (eds.) Positive Polynomials in Control, pp. 121\u2013133. Springer, Berlin (2005)"},{"issue":"1","key":"1465_CR11","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."},{"key":"1465_CR12","doi-asserted-by":"crossref","unstructured":"De Klerk, E., Postek, K., Kuhn, D.: Distributionally robust optimization with polynomial densities: theory, models and algorithms. To appear in Math. Program. Ser. B. arXiv:1805.03588 (2018)","DOI":"10.1007\/s10107-019-01429-5"},{"key":"1465_CR13","unstructured":"Fang, K., Fawzi, H.: The sum-of-squares hierarchy on the sphere, and applications in quantum information theory. arXiv:1908.05155 (2019)"},{"issue":"2","key":"1465_CR14","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1287\/moor.1060.0194","volume":"31","author":"AT Kalai","year":"2006","unstructured":"Kalai, A.T., Vempala, S.: Simulated annealing for convex optimization. Math. Oper. Res. 31(2), 253\u2013266 (2006)","journal-title":"Math. Oper. Res."},{"key":"1465_CR15","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."},{"issue":"3","key":"1465_CR16","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/100806990","volume":"21","author":"JB 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":"1465_CR17","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":"1465_CR18","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 T\u00faran. Can. J. Math. 17, 533\u2013540 (1965)","journal-title":"Can. J. Math."},{"key":"1465_CR19","unstructured":"Nesterov, Y.: Random walk in a simplex and quadratic optimization over convex polytopes. CORE Discussion Paper 2003\/71, CORE-UCL, Louvain-La-Neuve (2003)"},{"key":"1465_CR20","unstructured":"Parrilo, P.A.: Structured Semidefinite Programs and Semi-algebraic Geometry Methods in Robustness and Optimization. Ph.D. thesis, California Institute of Technology, Pasadena, California, USA (2000)"},{"issue":"2","key":"1465_CR21","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10107-003-0387-5","volume":"96","author":"PA Parrilo","year":"2003","unstructured":"Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. Ser. B 96(2), 293\u2013320 (2003)","journal-title":"Math. Program. Ser. B"},{"key":"1465_CR22","doi-asserted-by":"crossref","unstructured":"Reznick, B.: Some concrete aspects of Hilbert\u2019s 17th Problem. In: Real Algebraic Geometry and Ordered Structures (Baton Rouge, LA, 1996), pp. 251\u2013272. American Mathematical Society, Providence, RI (2000)","DOI":"10.1090\/conm\/253\/03936"},{"key":"1465_CR23","doi-asserted-by":"crossref","unstructured":"Slot, L., Laurent, M.: Improved convergence analysis of Lasserre\u2019s measure-based upper bounds for polynomial minimization on compact sets. arXiv:1905.08142 (2019)","DOI":"10.1007\/s10107-020-01468-3"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01465-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-019-01465-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01465-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T14:26:18Z","timestamp":1654871178000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-019-01465-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,21]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["1465"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01465-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,21]]},"assertion":[{"value":"18 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 December 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}