{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T18:03:23Z","timestamp":1777313003258,"version":"3.51.4"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2022,2,1]],"date-time":"2022-02-01T00:00:00Z","timestamp":1643673600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,1]],"date-time":"2022-02-01T00:00:00Z","timestamp":1643673600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010665","name":"H2020 Marie Sk\u0142odowska-Curie Actions","doi-asserted-by":"publisher","award":["813211"],"award-info":[{"award-number":["813211"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010665","name":"H2020 Marie Sk\u0142odowska-Curie Actions","doi-asserted-by":"publisher","award":["813211"],"award-info":[{"award-number":["813211"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the generalized moment problem (GMP) over the simplex and the sphere. This is a rich setting and it contains NP-hard problems as special cases, like constructing optimal cubature schemes and rational optimization. Using the reformulation-linearization technique (RLT) and Lasserre-type hierarchies, relaxations of the problem are introduced and analyzed. For our analysis we assume throughout the existence of a dual optimal solution as well as strong duality. For the GMP over the simplex we prove a convergence rate of <jats:italic>O<\/jats:italic>(1\/<jats:italic>r<\/jats:italic>) for a linear programming, RLT-type hierarchy, where <jats:italic>r<\/jats:italic> is the level of the hierarchy, using a quantitative version of P\u00f3lya\u2019s Positivstellensatz. As an extension of a recent result by Fang and Fawzi (Math Program, 2020. <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"doi\" xlink:href=\"10.1007\/s10107-020-01537-7\">https:\/\/doi.org\/10.1007\/s10107-020-01537-7<\/jats:ext-link>) we prove the Lasserre hierarchy of the GMP (Lasserre in Math Program 112(1):65\u201392, 2008. <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"doi\" xlink:href=\"10.1007\/s10107-006-0085-1\">https:\/\/doi.org\/10.1007\/s10107-006-0085-1<\/jats:ext-link>) over the sphere has a convergence rate of <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>. Moreover, we show the introduced linear RLT-relaxation is a generalization of a hierarchy for minimizing forms of degree <jats:italic>d<\/jats:italic> over the simplex, introduced by De Klerk et al. (J Theor Comput Sci 361(2\u20133):210\u2013225, 2006).\n<\/jats:p>","DOI":"10.1007\/s11590-022-01851-3","type":"journal-article","created":{"date-parts":[[2022,2,1]],"date-time":"2022-02-01T03:04:33Z","timestamp":1643684673000},"page":"2191-2208","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Convergence rates of RLT and Lasserre-type hierarchies for the generalized moment problem over the simplex and the sphere"],"prefix":"10.1007","volume":"16","author":[{"given":"Felix","family":"Kirschner","sequence":"first","affiliation":[]},{"given":"Etienne","family":"de Klerk","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,1]]},"reference":[{"issue":"1","key":"1851_CR1","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s10107-011-0499-2","volume":"137","author":"A Ahmadi","year":"2013","unstructured":"Ahmadi, A., Olshevsky, A., Parrilo, P., Tsitsiklis, J.: NP-hardness of deciding convexity of quartic polynomials and related problems. Math. Program. 137(1), 453\u2013476 (2013)","journal-title":"Math. Program."},{"key":"1851_CR2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1020209017701","author":"I Bomze","year":"2001","unstructured":"Bomze, I., Klerk, E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Glob. Optim. (2001). https:\/\/doi.org\/10.1023\/A:1020209017701","journal-title":"J. Glob. Optim."},{"issue":"4","key":"1851_CR3","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1007\/s10208-014-9197-9","volume":"15","author":"S Boyd","year":"2015","unstructured":"Boyd, S., Ryu, E.: Extensions of Gauss quadrature via linear programming. Found. Comput. Math. 15(4), 953\u2013971 (2015). https:\/\/doi.org\/10.1007\/s10208-014-9197-9","journal-title":"Found. Comput. Math."},{"key":"1851_CR4","first-page":"17","volume-title":"A Survey of Semidefinite Programming Approaches to the Generalized Problem of Moments and Their Error Analysis. 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. Association for Women in Mathematics Series, pp. 17\u201356. Springer, Berlin (2019)"},{"issue":"2\u20133","key":"1851_CR5","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 fixed degree over the simplex. Theor. Comput. Sci. 361(2\u20133), 210\u2013225 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"1851_CR6","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)"},{"key":"1851_CR7","doi-asserted-by":"publisher","unstructured":"Dunkl, C., Xu, Y.: Orthogonal polynomials of several variables. In: Encyclopedia of Mathematics and Its Applications, 2 edn. Cambridge University Press (2014). https:\/\/doi.org\/10.1017\/CBO9781107786134","DOI":"10.1017\/CBO9781107786134"},{"key":"1851_CR8","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."},{"key":"1851_CR9","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s10107-005-0589-0","volume":"106","author":"D Jibetean","year":"2006","unstructured":"Jibetean, D., Klerk, E.: Global optimization of rational functions: a semidefinite programming approach. Math. Program. 106, 93\u2013109 (2006). https:\/\/doi.org\/10.1007\/s10107-005-0589-0","journal-title":"Math. Program."},{"issue":"1","key":"1851_CR10","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s10107-006-0085-1","volume":"112","author":"JB Lasserre","year":"2008","unstructured":"Lasserre, J.B.: A semidefinite programming approach to the generalized problem of moments. Math. Program. 112(1), 65\u201392 (2008). https:\/\/doi.org\/10.1007\/s10107-006-0085-1","journal-title":"Math. Program."},{"key":"1851_CR11","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). https:\/\/doi.org\/10.1142\/p665"},{"key":"1851_CR12","doi-asserted-by":"publisher","first-page":"533","DOI":"10.4153\/CJM-1965-053-6","volume":"17","author":"M Motzkin","year":"1965","unstructured":"Motzkin, M., Straus, E.: 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":"1851_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0603-3","volume-title":"An Introduction to Banach Space Theory","author":"R Megginson","year":"1998","unstructured":"Megginson, R.: An Introduction to Banach Space Theory. Springer, Berlin (1998)"},{"key":"1851_CR14","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). https:\/\/doi.org\/10.1016\/j.jco.2006.07.002","journal-title":"J. Complex."},{"issue":"1\u20132","key":"1851_CR15","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/S0022-4049(00)00155-9","volume":"164","author":"V Powers","year":"2001","unstructured":"Powers, V., Reznick, B.: A new bound for P\u00f3lya\u2019s Theorem with applications to polynomials positive on polyhedra. J. Pure Appl. Algebra 164(1\u20132), 221\u2013229 (2001). https:\/\/doi.org\/10.1016\/S0022-4049(00)00155-9. (Copyright: Copyright 2005 Elsevier B.V., All rights reserved)","journal-title":"J. Pure Appl. Algebra"},{"key":"1851_CR16","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BF02572604","volume":"220","author":"B Reznick","year":"1995","unstructured":"Reznick, B.: Uniform denominators in Hilbert\u2019s seventeenth problem. Math. Z. 220, 75\u201397 (1995)","journal-title":"Math. Z."},{"key":"1851_CR17","doi-asserted-by":"crossref","unstructured":"Reznick, B.: Some concrete aspects of Hilbert\u2019s 17th Problem. In: In Contemporary Mathematics, pp. 251\u2013272. American Mathematical Society (1996)","DOI":"10.1090\/conm\/253\/03936"},{"key":"1851_CR18","doi-asserted-by":"publisher","unstructured":"Shapiro, A.: On duality theory of conic linear problems. Semi-Infinite Programming pp. 135\u2013165 (2000). https:\/\/doi.org\/10.1007\/978-1-4757-3403-47","DOI":"10.1007\/978-1-4757-3403-47"},{"key":"1851_CR19","volume-title":"A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, Nonconvex Optimization and Its Applications","author":"H Sherali","year":"1999","unstructured":"Sherali, H., Adams, W.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, Nonconvex Optimization and Its Applications, vol. 31. Springer, Berlin (1999)"},{"key":"1851_CR20","first-page":"123","volume":"81","author":"V Tchakaloff","year":"1957","unstructured":"Tchakaloff, V.: Formules de cubature \u1e3fecanique c\u00f3efficients nonn\u00e9gatifs. Bulletin des Sciences Math\u00e9matiques 81, 123\u2013134 (1957)","journal-title":"Bulletin des Sciences Math\u00e9matiques"},{"key":"1851_CR21","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.cam.2014.01.007","volume":"266","author":"D Williams","year":"2014","unstructured":"Williams, D., Shunn, L., Jameson, A.: Symmetric quadrature rules for simplexes based on sphere closed packed lattice arrangements. J. Comput. Appl. Math. 266, 18\u201338 (2014). https:\/\/doi.org\/10.1016\/j.cam.2014.01.007. (Copyright: Copyright 2014 Elsevier B.V., All rights reserved)","journal-title":"J. Comput. Appl. Math."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01851-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-022-01851-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01851-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T12:58:13Z","timestamp":1665061093000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-022-01851-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,1]]},"references-count":21,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["1851"],"URL":"https:\/\/doi.org\/10.1007\/s11590-022-01851-3","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,1]]},"assertion":[{"value":"3 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}