{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T21:40:29Z","timestamp":1769722829279,"version":"3.49.0"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T00:00:00Z","timestamp":1746144000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T00:00:00Z","timestamp":1746144000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2110780"],"award-info":[{"award-number":["2110780"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>This paper studies the sparse Moment-SOS hierarchy of relaxations for solving sparse polynomial optimization problems. We show that this sparse hierarchy is tight if and only if the objective can be written as a sum of sparse nonnegative polynomials, each of which belongs to the sum of the ideal and quadratic module generated by the corresponding sparse constraints. Based on this characterization, we give several sufficient conditions for the sparse Moment-SOS hierarchy to be tight. In particular, we show that this sparse hierarchy is tight under some assumptions such as convexity, optimality conditions or finiteness of constraining sets.<\/jats:p>","DOI":"10.1007\/s10107-025-02223-2","type":"journal-article","created":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T09:51:54Z","timestamp":1746179514000},"page":"369-405","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A characterization for tightness of the sparse Moment-SOS hierarchy"],"prefix":"10.1007","volume":"215","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2637-8274","authenticated-orcid":false,"given":"Jiawang","family":"Nie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zheng","family":"Qu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xindong","family":"Tang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Linghao","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,2]]},"reference":[{"key":"2223_CR1","unstructured":"ApS, M.: Mosek Optimization Toolbox for Matlab: User\u2019s Guide and Reference Manual. Version 4.1 (2019)"},{"key":"2223_CR2","doi-asserted-by":"crossref","unstructured":"Blair, J.R.S., Peyton, B.: An introduction to chordal graphs and clique trees. In: George, A., Gilbert, J.R., Liu, J.W.H. (eds.) Graph Theory and Sparse 836 Matrix Computation. Springer, New York, pp. 1\u201329 (1993)","DOI":"10.1007\/978-1-4613-8369-7_1"},{"key":"2223_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03718-8","volume-title":"Real Algebraic Geometry","author":"J Bochnak","year":"1998","unstructured":"Bochnak, J., Coste, M., Roy, M.-F.: Real Algebraic Geometry. Springer, Berlin (1998)"},{"key":"2223_CR4","unstructured":"Curto, R.E., Fialkow, L.A.: Truncated K-moment problems in several variables. J. Oper. Theory, pp. 189\u2013226 (2005)"},{"issue":"3","key":"2223_CR5","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1137\/100814147","volume":"21","author":"E De Klerk","year":"2011","unstructured":"De Klerk, E., Laurent, M.: On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems. SIAM J. Optim. 21(3), 824\u2013832 (2011)","journal-title":"SIAM J. Optim."},{"key":"2223_CR6","doi-asserted-by":"publisher","DOI":"10.1142\/q0252","volume-title":"The Moment-SOS Hierarchy","author":"D Henrion","year":"2020","unstructured":"Henrion, D., Korda, M., Lasserre, J.B.: The Moment-SOS Hierarchy. World Scientific, Singapore (2020)"},{"key":"2223_CR7","doi-asserted-by":"crossref","unstructured":"Henrion, D., Lasserre, J.B.: Detecting global optimality and extracting solutions in GloptiPoly. In: Positive Polynomials in Control, pp. 293\u2013310. Springer (2005)","DOI":"10.1007\/10997703_15"},{"issue":"4\u20135","key":"2223_CR8","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1080\/10556780802699201","volume":"24","author":"D Henrion","year":"2009","unstructured":"Henrion, D., Lasserre, J.B., L\u00f6fberg, J.: Gloptipoly 3: moments, optimization and semidefinite programming. Optim. Methods Softw. 24(4\u20135), 761\u2013779 (2009)","journal-title":"Optim. Methods Softw."},{"issue":"2","key":"2223_CR9","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1137\/24M1636010","volume":"35","author":"L Huang","year":"2025","unstructured":"Huang, L., Kang, S., Wang, J., Yang, H.: Sparse polynomial optimization with unbounded sets. SIAM J. Optim. 35(2), 593\u2013621 (2025)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"2223_CR10","doi-asserted-by":"publisher","first-page":"3399","DOI":"10.1137\/23M1605430","volume":"34","author":"L Huang","year":"2024","unstructured":"Huang, L., Nie, J., Yuan, Y.-X.: Finite convergence of moment-SOS relaxations with non-real radical ideals. SIAM J. Optim. 34(4), 3399\u20133428 (2024)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"2223_CR11","doi-asserted-by":"publisher","first-page":"1128","DOI":"10.1137\/140962425","volume":"26","author":"S Iliman","year":"2016","unstructured":"Iliman, S., De Wolff, T.: Lower bounds for polynomials with simplex newton polytopes based on geometric programming. SIAM J. Optim. 26(2), 1128\u20131146 (2016)","journal-title":"SIAM J. Optim."},{"key":"2223_CR12","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1007\/s10107-020-01610-1","volume":"193","author":"I Klep","year":"2022","unstructured":"Klep, I., Magron, V., Povh, J.: Sparse noncommutative polynomial optimization. Math. Program. 193, 789\u2013829 (2022)","journal-title":"Math. Program."},{"key":"2223_CR13","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s10589-007-9112-2","volume":"42","author":"M Kojima","year":"2009","unstructured":"Kojima, M., Muramatsu, M.: A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones. Comput. Optim. Appl. 42, 31\u201341 (2009)","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"2223_CR14","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1007\/s10107-023-01993-x","volume":"205","author":"M Korda","year":"2024","unstructured":"Korda, M., Laurent, M., Magron, V., Steenkamp, A.: Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks. Math. Program. 205(1), 703\u2013744 (2024)","journal-title":"Math. Program."},{"issue":"1","key":"2223_CR15","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/s10107-024-02071-6","volume":"209","author":"M Korda","year":"2025","unstructured":"Korda, M., Magron, V., Rios-Zertuche, R.: Convergence rates for sums-of-squares hierarchies with correlative sparsity. Math. Program. 209(1), 435\u2013473 (2025)","journal-title":"Math. Program."},{"issue":"3","key":"2223_CR16","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":"3","key":"2223_CR17","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1137\/05064504X","volume":"17","author":"JB Lasserre","year":"2006","unstructured":"Lasserre, J.B.: Convergent SDP-relaxations in polynomial optimization with sparsity. SIAM J. Optim. 17(3), 822\u2013843 (2006)","journal-title":"SIAM J. Optim."},{"key":"2223_CR18","doi-asserted-by":"publisher","first-page":"1995","DOI":"10.1137\/080728214","volume":"19","author":"JB Lasserre","year":"2009","unstructured":"Lasserre, J.B.: Convexity in semi-algebraic geometry and polynomial optimization. SIAM J. Optim. 19, 1995\u20132014 (2009)","journal-title":"SIAM J. Optim."},{"key":"2223_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107447226","volume-title":"An Introduction to Polynomial and Semi-algebraic Optimization","author":"JB Lasserre","year":"2015","unstructured":"Lasserre, J.B.: An Introduction to Polynomial and Semi-algebraic Optimization. Cambridge University Press, Cambridge (2015)"},{"issue":"10","key":"2223_CR20","doi-asserted-by":"publisher","first-page":"2965","DOI":"10.1090\/S0002-9939-05-08133-5","volume":"133","author":"M Laurent","year":"2005","unstructured":"Laurent, M.: Revisiting two theorems of Curto and Fialkow on moment matrices. Proc. AMS 133(10), 2965\u20132976 (2005)","journal-title":"Proc. AMS"},{"key":"2223_CR21","doi-asserted-by":"crossref","unstructured":"Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Emerging Applications of Algebraic Geometry of IMA Volumes in Mathematics and its Applications, vol. 149, pp. 157\u2013270, Springer (2009)","DOI":"10.1007\/978-0-387-09686-5_7"},{"key":"2223_CR22","doi-asserted-by":"crossref","unstructured":"L\u00f6fberg, J.: YALMIP: a toolbox for modeling and optimization in MATLAB. In: 2004 IEEE International Conference on Robotics and Automation, pp. 284\u2013289. IEEE (2004)","DOI":"10.1109\/CACSD.2004.1393890"},{"key":"2223_CR23","unstructured":"Magron, V., Wang, J.: TSSOS: a Julia library to exploit sparsity for large-scale polynomial optimization (2021). arXiv preprint arXiv:2103.00915"},{"key":"2223_CR24","doi-asserted-by":"publisher","DOI":"10.1142\/q0382","volume-title":"Sparse Polynomial Optimization: Theory and Practice","author":"V Magron","year":"2023","unstructured":"Magron, V., Wang, J.: Sparse Polynomial Optimization: Theory and Practice. World Scientific, Singapore (2023)"},{"key":"2223_CR25","doi-asserted-by":"crossref","unstructured":"Marshall, M.: Positive Polynomials and Sums of Squares. Number 146. American Mathematical Society (2008)","DOI":"10.1090\/surv\/146"},{"key":"2223_CR26","doi-asserted-by":"publisher","first-page":"1703","DOI":"10.1007\/s10208-021-09497-w","volume":"21","author":"R Murray","year":"2021","unstructured":"Murray, R., Chandrasekaran, V., Wierman, A.: Newton polytopes and relative entropy optimization. Found. Comput. Math. 21, 1703\u20131737 (2021)","journal-title":"Found. Comput. Math."},{"key":"2223_CR27","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s12532-020-00193-4","volume":"13","author":"R Murray","year":"2021","unstructured":"Murray, R., Chandrasekaran, V., Wierman, A.: Signomial and polynomial optimization via relative entropy and partial dualization. Math. Prog. Comput. 13, 257\u2013295 (2021)","journal-title":"Math. Prog. Comput."},{"key":"2223_CR28","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2023.111233","volume":"157","author":"M Newton","year":"2023","unstructured":"Newton, M., Papachristodoulou, A.: Sparse polynomial optimisation for neural network verification. Automatica 157, 111233 (2023)","journal-title":"Automatica"},{"key":"2223_CR29","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/s10107-012-0589-9","volume":"142","author":"J Nie","year":"2013","unstructured":"Nie, J.: Certifying convergence of Lasserre\u2019s hierarchy via flat truncation. Math. Program. 142, 485\u2013510 (2013)","journal-title":"Math. Program."},{"issue":"3","key":"2223_CR30","doi-asserted-by":"publisher","first-page":"1634","DOI":"10.1137\/120898772","volume":"23","author":"J Nie","year":"2013","unstructured":"Nie, J.: Polynomial optimization with real varieties. SIAM J. Optim. 23(3), 1634\u20131646 (2013)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"2223_CR31","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":"2223_CR32","doi-asserted-by":"crossref","unstructured":"Nie, J.: Moment and Polynomial Optimization. SIAM (2023)","DOI":"10.1137\/1.9781611977608"},{"issue":"4","key":"2223_CR33","doi-asserted-by":"publisher","first-page":"1534","DOI":"10.1137\/060668791","volume":"19","author":"J Nie","year":"2009","unstructured":"Nie, J., Demmel, J.: Sparse SOS relaxations for minimizing functions that are summations of small polynomials. SIAM J. Optim. 19(4), 1534\u20131558 (2009)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"2223_CR34","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1137\/22M1515689","volume":"34","author":"Z Qu","year":"2024","unstructured":"Qu, Z., Tang, X.: A correlatively sparse Lagrange multiplier expression relaxation for polynomial optimization. SIAM J. Optim. 34(1), 127\u2013162 (2024)","journal-title":"SIAM J. Optim."},{"key":"2223_CR35","unstructured":"Vargas, L.: On the hardness of deciding the finite convergence of Lasserre hierarchies. Numer. Algebra Control Optim., To appear (2024)"},{"issue":"1","key":"2223_CR36","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1137\/050623802","volume":"17","author":"H Waki","year":"2006","unstructured":"Waki, H., Kim, S., Kojima, M., Muramatsu, M.: Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim. 17(1), 218\u2013242 (2006)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"2223_CR37","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/s10589-021-00301-7","volume":"80","author":"J Wang","year":"2021","unstructured":"Wang, J., Magron, V.: Exploiting term sparsity in noncommutative polynomial optimization. Comput. Optim. Appl. 80(2), 483\u2013521 (2021)","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"2223_CR38","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/19M1307871","volume":"31","author":"J Wang","year":"2021","unstructured":"Wang, J., Magron, V., Lasserre, J.B.: TSSOS: a moment-SOS hierarchy that exploits term sparsity. SIAM J. Optim. 31(1), 30\u201358 (2021)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"2223_CR39","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1137\/20M1323564","volume":"31","author":"J Wang","year":"2021","unstructured":"Wang, J., Magron, V., Lasserre, J.B.: Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension. SIAM J. Optim. 31(1), 114\u2013141 (2021)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"2223_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3569709","volume":"48","author":"J Wang","year":"2022","unstructured":"Wang, J., Magron, V., Lasserre, J.B., Mai, N.H.A.: CS-TSSOS: correlative and term sparsity for large-scale polynomial optimization. ACM Trans. Math. Softw. 48(4), 1\u201326 (2022)","journal-title":"ACM Trans. Math. Softw."},{"key":"2223_CR41","doi-asserted-by":"publisher","DOI":"10.1016\/j.epsr.2022.108683","volume":"213","author":"J Wang","year":"2022","unstructured":"Wang, J., Magron, V., Lasserre, J.B.: Certifying global optimality of AC-OPF solutions via sparse polynomial optimization. Electric Power Syst. Res. 213, 108683 (2022)","journal-title":"Electric Power Syst. Res."},{"key":"2223_CR42","doi-asserted-by":"crossref","unstructured":"Yang, H., Carlone, L.: In perfect shape: certifiably optimal 3D shape reconstruction from 2D landmarks. In: Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition, pp. 621\u2013630 (2020)","DOI":"10.1109\/CVPR42600.2020.00070"},{"key":"2223_CR43","unstructured":"Yang, J., Dura\u0161inovi\u0107, S., Lasserre, J.B., Magron, V., Zhao, J.: Verifying properties of binary neural networks using sparse polynomial optimization (2024). arXiv preprint arXiv:2405.17049"},{"issue":"4","key":"2223_CR44","doi-asserted-by":"publisher","first-page":"1667","DOI":"10.1137\/22M1539137","volume":"44","author":"A Zhou","year":"2023","unstructured":"Zhou, A., Liu, K., Fan, J.: Semidefinite relaxation methods for tensor absolute value equations. SIAM J. Matrix Anal. Appl. 44(4), 1667\u20131692 (2023)","journal-title":"SIAM J. Matrix Anal. Appl."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02223-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-025-02223-2","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02223-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T12:21:03Z","timestamp":1768047663000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-025-02223-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,2]]},"references-count":44,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["2223"],"URL":"https:\/\/doi.org\/10.1007\/s10107-025-02223-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,2]]},"assertion":[{"value":"13 June 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 May 2025","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 have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}