{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T23:02:49Z","timestamp":1773097369481,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,9,15]],"date-time":"2022-09-15T00:00:00Z","timestamp":1663200000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,9,15]],"date-time":"2022-09-15T00:00:00Z","timestamp":1663200000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["764759"],"award-info":[{"award-number":["764759"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2023,4]]},"abstract":"Abstract<\/jats:title>Let $$S \\subseteq \\mathbb {R}^n$$<\/jats:tex-math>\n \n S<\/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> be a compact semialgebraic set and let f<\/jats:italic> be a polynomial nonnegative on S<\/jats:italic>. Schm\u00fcdgen\u2019s Positivstellensatz then states that for any $$\\eta > 0$$<\/jats:tex-math>\n \n \u03b7<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the nonnegativity of $$f + \\eta$$<\/jats:tex-math>\n \n f<\/mml:mi>\n +<\/mml:mo>\n \u03b7<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> on S<\/jats:italic> can be certified by expressing $$f + \\eta$$<\/jats:tex-math>\n \n f<\/mml:mi>\n +<\/mml:mo>\n \u03b7<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> as a conic combination of products of the polynomials that occur in the inequalities defining S<\/jats:italic>, where the coefficients are (globally nonnegative) sum-of-squares polynomials. It does not, however, provide explicit bounds on the degree of the polynomials required for such an expression. We show that in the special case where $$S = [-1, 1]^n$$<\/jats:tex-math>\n \n S<\/mml:mi>\n =<\/mml:mo>\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:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the hypercube, a Schm\u00fcdgen-type certificate of nonnegativity exists involving only polynomials of degree $$O(1 \/ \\sqrt{\\eta })$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n \n \u03b7<\/mml:mi>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This improves quadratically upon the previously best known estimate in $$O(1\/\\eta )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n \u03b7<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our proof relies on an application of the polynomial kernel method, making use in particular of the Jackson kernel on the interval $$[-1, 1]$$<\/jats:tex-math>\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 <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s11590-022-01922-5","type":"journal-article","created":{"date-parts":[[2022,9,15]],"date-time":"2022-09-15T03:30:25Z","timestamp":1663212625000},"page":"515-530","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["An effective version of Schm\u00fcdgen\u2019s Positivstellensatz for the hypercube"],"prefix":"10.1007","volume":"17","author":[{"given":"Monique","family":"Laurent","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3790-492X","authenticated-orcid":false,"given":"Lucas","family":"Slot","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,15]]},"reference":[{"issue":"3","key":"1922_CR1","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(3), 796\u2013817 (2001)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1922_CR2","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(2), 203\u2013206 (1991)","journal-title":"Math. Ann."},{"key":"1922_CR3","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1103\/RevModPhys.78.275","volume":"78","author":"A Wei\u00dfe","year":"2006","unstructured":"Wei\u00dfe, A., Wellein, G., Alvermann, A., Fehske, H.: The kernel polynomial method. Rev. Mod. Phys. 78, 275 (2006)","journal-title":"Rev. Mod. Phys."},{"key":"1922_CR4","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":"1922_CR5","doi-asserted-by":"crossref","unstructured":"Slot, L., Laurent, M.: Sum-of-squares hierarchies for binary polynomial optimization. Singh M., Williamson D.P. (eds) Integer Programming and Combinatorial Optimization (IPCO 2021). Lecture Notes in Computer Science","DOI":"10.1007\/978-3-030-73879-2_4"},{"issue":"1","key":"1922_CR6","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1137\/16M1065264","volume":"27","author":"E de Klerk","year":"2017","unstructured":"de Klerk, E., Hess, R., Laurent, M.: Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization. SIAM J. Opti. 27(1), 347\u2013367 (2017)","journal-title":"SIAM J. Opti."},{"issue":"4","key":"1922_CR7","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\u2019s Positivstellensatz. J. Complex. 20(4), 529\u2013543 (2004)","journal-title":"J. Complex."},{"key":"1922_CR8","unstructured":"P\u00f3lya, G.: Uber positive Darstellung von Polynomen. Vierteljahresschrift der Naturforschenden Gesellschaft in Z\u00fcrich, 73, 14\u2013145, 1928. Reprinted. In: Collected Papers. Vol 2, pp. 309\u2013313. MIT Press, Cambridge (1974)"},{"issue":"1\u20132","key":"1922_CR9","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)","journal-title":"J. Pure Appl. Algebra"},{"issue":"6","key":"1922_CR10","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. on Optim. 20(6), 3104\u20133120 (2010)","journal-title":"SIAM J. on Optim."},{"key":"1922_CR11","unstructured":"Szeg\u00f6, G.: Orthogonal Polynomials. vol. 23 in American Mathematical Society colloquium publications"},{"key":"1922_CR12","doi-asserted-by":"publisher","first-page":"4677","DOI":"10.1090\/S0002-9947-00-02595-2","volume":"352","author":"V Powers","year":"2000","unstructured":"Powers, V., Reznick, B.: Polynomials that are positive on an interval. Trans. Amer. Math. Soc. 352, 4677\u20134692 (2000)","journal-title":"Trans. Amer. Math. Soc."},{"issue":"1","key":"1922_CR13","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":"1922_CR14","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s10107-020-01586-y","volume":"188","author":"L Slot","year":"2021","unstructured":"Slot, L., Laurent, M.: Near-optimal analysis of univariate moment bounds for polynomial optimization. Math. Program. 188, 443\u2013460 (2021)","journal-title":"Math. Program."},{"issue":"1","key":"1922_CR15","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(1), 135\u2013150 (2007)","journal-title":"J. Complex."},{"key":"1922_CR16","doi-asserted-by":"crossref","unstructured":"Baldi, L., Mourrain, B.: On moment approximation and the effective Putinar\u2019s Positivstellensatz, arXiv:2111.11258, 2021","DOI":"10.1007\/s10107-022-01877-6"},{"issue":"1","key":"1922_CR17","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10107-013-0680-x","volume":"146","author":"J Nie","year":"2014","unstructured":"Nie, J.: Optimality conditions and finite convergence of Lasserre\u2019s hierarchy. Math. program. 146(1), 97\u2013121 (2014)","journal-title":"Math. program."},{"key":"1922_CR18","unstructured":"Mai, N.H.A., Magron V.: On the complexity of Putinar-Vasilescu\u2019s Positivstellensatz. Journal of Complexity, 10.1016\/j.jco.2022.101663"},{"key":"1922_CR19","doi-asserted-by":"crossref","unstructured":"Magron, V.: Error bounds for polynomial optimization over the hypercube using Putinar type representations. arXiv:1404.6145, 2014","DOI":"10.1007\/s11590-014-0797-8"},{"issue":"3","key":"1922_CR20","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/s40305-013-0017-8","volume":"1","author":"J Nie","year":"2013","unstructured":"Nie, J.: An approximation bound analysis for Lasserre\u2019s relaxation. J. Oper. Res. Soc. China 1(3), 313\u2013332 (2013)","journal-title":"J. Oper. Res. Soc. China"},{"key":"1922_CR21","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1006\/jcom.1996.0011","volume":"12","author":"G Stengle","year":"1996","unstructured":"Stengle, G.: Complexity Estimates for the Schm\u00fcdgen Positivstellensatz. J. Complex. 12, 167\u2013174 (1996)","journal-title":"J. Complex."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01922-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-022-01922-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01922-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,8]],"date-time":"2023-03-08T12:18:38Z","timestamp":1678277918000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-022-01922-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,15]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["1922"],"URL":"https:\/\/doi.org\/10.1007\/s11590-022-01922-5","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,15]]},"assertion":[{"value":"21 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 August 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}