{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T18:57:28Z","timestamp":1775069848156,"version":"3.50.1"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,7,27]],"date-time":"2021-07-27T00:00:00Z","timestamp":1627344000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,7,27]],"date-time":"2021-07-27T00:00:00Z","timestamp":1627344000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-18-ERC2-0004-01 ANR-19-PI3A-0004"],"award-info":[{"award-number":["ANR-18-ERC2-0004-01 ANR-19-PI3A-0004"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010665","name":"H2020 Marie Sklodowska-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":["Comput Optim Appl"],"published-print":{"date-parts":[[2021,11]]},"DOI":"10.1007\/s10589-021-00301-7","type":"journal-article","created":{"date-parts":[[2021,7,27]],"date-time":"2021-07-27T16:03:36Z","timestamp":1627401816000},"page":"483-521","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Exploiting term sparsity in noncommutative polynomial optimization"],"prefix":"10.1007","volume":"80","author":[{"given":"Jie","family":"Wang","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1147-3738","authenticated-orcid":false,"given":"Victor","family":"Magron","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,27]]},"reference":[{"key":"301_CR1","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0024-3795(88)90240-6","volume":"107","author":"J Agler","year":"1988","unstructured":"Agler, J., Helton, W., McCullough, S., Rodman, L.: Positive semidefinite matrices with a given sparsity pattern. Linear Algebra Appl. 107, 101\u2013149 (1988)","journal-title":"Linear Algebra Appl."},{"key":"301_CR2","unstructured":"Anjos, M.F., Lasserre, J.B. (eds.): Handbook on semidefinite, conic and polynomial optimization. International Series in Operations Research & Management Science"},{"key":"301_CR3","unstructured":"ApS, M.: The MOSEK optimization toolbox. Version 8.1. (2017). http:\/\/docs.mosek.com\/8.1\/toolbox\/index.html"},{"issue":"1","key":"301_CR4","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1137\/141000671","volume":"59","author":"J Bezanson","year":"2017","unstructured":"Bezanson, J., Edelman, A., Karpinski, S., Shah, V.B.: Julia: a fresh approach to numerical computing. SIAM Rev. 59(1), 65\u201398 (2017)","journal-title":"SIAM Rev."},{"key":"301_CR5","doi-asserted-by":"crossref","unstructured":"Blair, J.R., Peyton, B.: An introduction to chordal graphs and clique trees. In: Graph Theory and Sparse Matrix Computation. pp. 1\u201329. Springer (1993)","DOI":"10.1007\/978-1-4613-8369-7_1"},{"issue":"3","key":"301_CR6","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.ic.2009.03.008","volume":"208","author":"HL Bodlaender","year":"2010","unstructured":"Bodlaender, H.L., Koster, A.M.: Treewidth computations I: upper bounds. Inf. Comput. 208(3), 259\u2013275 (2010)","journal-title":"Inf. Comput."},{"key":"301_CR7","unstructured":"Bromberger, S., Fairbanks, J., other contributors: JuliaGraphs\/LightGraphs.jl: an optimized graphs package for the julia programming language (2017). 10.5281\/zenodo.889971"},{"issue":"1","key":"301_CR8","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/s12532-015-0089-z","volume":"8","author":"F Bugarin","year":"2016","unstructured":"Bugarin, F., Henrion, D., Lasserre, J.B.: Minimizing the sum of many rational functions. Math. Programm. Comput. 8(1), 83\u2013111 (2016)","journal-title":"Math. Programm. Comput."},{"issue":"1\u20132","key":"301_CR9","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/s10107-011-0505-8","volume":"137","author":"S Burgdorf","year":"2013","unstructured":"Burgdorf, S., Cafuta, K., Klep, I., Povh, J.: The tracial moment problem and trace-optimization of polynomials. Math. Program. 137(1\u20132), 557\u2013578 (2013). https:\/\/doi.org\/10.1007\/s10107-011-0505-8","journal-title":"Math. Program."},{"issue":"1","key":"301_CR10","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/s10107-011-0505-8","volume":"137","author":"S Burgdorf","year":"2013","unstructured":"Burgdorf, S., Cafuta, K., Klep, I., Povh, J.: The tracial moment problem and trace-optimization of polynomials. Math. Program. 137(1), 557\u2013578 (2013)","journal-title":"Math. Program."},{"key":"301_CR11","doi-asserted-by":"crossref","unstructured":"Burgdorf, S., Klep, I., Povh, J.: Optimization of polynomials in non-commuting variables, vol. 2. Springer, bERLIN (2016)","DOI":"10.1007\/978-3-319-33338-0"},{"issue":"2","key":"301_CR12","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1137\/110830733","volume":"22","author":"K Cafuta","year":"2012","unstructured":"Cafuta, K., Klep, I., Povh, J.: Constrained polynomial optimization problems with noncommuting variables. SIAM J. Optim. 22(2), 363\u2013383 (2012). https:\/\/doi.org\/10.1137\/110830733","journal-title":"SIAM J. Optim."},{"key":"301_CR13","unstructured":"Chen, T., Lasserre, J.B., Magron, V., Pauwels, E.: Polynomial optimization for bounding Lipschitz constants of deep networks. arXiv preprint arXiv:2002.03657 (2020)"},{"issue":"2","key":"301_CR14","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1137\/15M1020575","volume":"59","author":"I Dunning","year":"2017","unstructured":"Dunning, I., Huchette, J., Lubin, M.: JuMP: A modeling language for mathematical optimization. SIAM Rev. 59(2), 295\u2013320 (2017)","journal-title":"SIAM Rev."},{"issue":"5","key":"301_CR15","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1007\/s10208-018-09410-y","volume":"19","author":"S Gribling","year":"2019","unstructured":"Gribling, S., De Laat, D., Laurent, M.: Lower bounds on matrix factorization ranks via noncommutative polynomial optimization. Found. Comput. Math. 19(5), 1013\u20131070 (2019)","journal-title":"Found. Comput. Math."},{"issue":"1","key":"301_CR16","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s10107-018-1287-z","volume":"170","author":"S Gribling","year":"2018","unstructured":"Gribling, S., de Laat, D., Laurent, M.: Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization. Math. Program. 170(1), 5\u201342 (2018)","journal-title":"Math. Program."},{"key":"301_CR17","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0024-3795(84)90207-6","volume":"58","author":"R Grone","year":"1984","unstructured":"Grone, R., Johnson, C.R., S\u00e1, E.M., Wolkowicz, H.: Positive definite completions of partial Hermitian matrices. Linear Algebra Appl. 58, 109\u2013124 (1984)","journal-title":"Linear Algebra Appl."},{"issue":"9","key":"301_CR18","doi-asserted-by":"publisher","first-page":"3721","DOI":"10.1090\/S0002-9947-04-03433-6","volume":"356","author":"J Helton","year":"2004","unstructured":"Helton, J., McCullough, S.: A Positivstellensatz for non-commutative polynomials. Trans. Am. Math. Soc. 356(9), 3721\u20133737 (2004)","journal-title":"Trans. Am. Math. Soc."},{"key":"301_CR19","doi-asserted-by":"publisher","first-page":"675","DOI":"10.2307\/3597203","volume":"156","author":"JW Helton","year":"2002","unstructured":"Helton, J.W.: Positive noncommutative polynomials are sums of squares. Ann. Math. 156, 675\u2013694 (2002)","journal-title":"Ann. Math."},{"issue":"2","key":"301_CR20","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1137\/15M1034386","volume":"28","author":"C Josz","year":"2018","unstructured":"Josz, C., Molzahn, D.K.: Lasserre hierarchy for large scale polynomial optimization in real and complex variables. SIAM J. Optim. 28(2), 1017\u20131048 (2018)","journal-title":"SIAM J. Optim."},{"key":"301_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01610-1","author":"I Klep","year":"2021","unstructured":"Klep, I., Magron, V., Povh, J.: Sparse noncommutative polynomial optimization. Math Programm. (2021). https:\/\/doi.org\/10.1007\/s10107-020-01610-1","journal-title":"Sparse noncommutative polynomial optimization. Math Programm."},{"key":"301_CR22","doi-asserted-by":"crossref","unstructured":"Klep, I., Magron, V., Vol\u010di\u010d, J.: Optimization over trace polynomials. arXiv preprint arXiv:2006.12510 (2020)","DOI":"10.1007\/s00023-021-01095-4"},{"issue":"3","key":"301_CR23","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":"301_CR24","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":"301_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-09686-5_7","author":"M Laurent","year":"2009","unstructured":"Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. Emerg. Appl. Algebr. Geom. (2009). https:\/\/doi.org\/10.1007\/978-0-387-09686-5_7","journal-title":"Emerg. Appl. Algebr. Geom."},{"issue":"4","key":"301_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3206430","volume":"44","author":"V Magron","year":"2018","unstructured":"Magron, V.: Interval enclosures of upper bounds of roundoff errors using semidefinite programming. ACM Trans. Math. Softw. 44(4), 1\u201318 (2018)","journal-title":"ACM Trans. Math. Softw."},{"issue":"4","key":"301_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3015465","volume":"43","author":"V Magron","year":"2017","unstructured":"Magron, V., Constantinides, G., Donaldson, A.: Certified roundoff error bounds using semidefinite programming. ACM Trans. Math. Softw. 43(4), 1\u201334 (2017)","journal-title":"ACM Trans. Math. Softw."},{"key":"301_CR28","unstructured":"Mai, N.H.A., Lasserre, J.B., Magron, V., Wang, J.: Exploiting constant trace property in large-scale polynomial optimization. arXiv preprint arXiv:2012.08873 (2020)"},{"key":"301_CR29","unstructured":"Mai, N.H.A., Magron, V., Lasserre, J.B.: A sparse version of Reznick\u2019s Positivstellensatz. arXiv preprint arXiv:2002.05101 (2020)"},{"key":"301_CR30","unstructured":"Marecek, J., Vala, J.: Quantum optimal control via magnus expansion: The non-commutative polynomial optimization problem. arXiv preprint arXiv:2001.06464 (2020)"},{"issue":"7","key":"301_CR31","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/10\/7\/073013","volume":"10","author":"M Navascu\u00e9s","year":"2008","unstructured":"Navascu\u00e9s, M., Pironio, S., Ac\u00edn, A.: A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New J. Phys. 10(7), 073013 (2008)","journal-title":"New J. Phys."},{"issue":"2","key":"301_CR32","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.79.022120","volume":"79","author":"KF P\u00e1l","year":"2009","unstructured":"P\u00e1l, K.F., V\u00e9rtesi, T.: Quantum bounds on Bell inequalities. Phys. Rev. A 79(2), 022120 (2009)","journal-title":"Phys. Rev. A"},{"issue":"5","key":"301_CR33","doi-asserted-by":"publisher","first-page":"2157","DOI":"10.1137\/090760155","volume":"20","author":"S Pironio","year":"2010","unstructured":"Pironio, S., Navascu\u00e9s, M., Ac\u00edn, A.: Convergent relaxations of polynomial optimization problems with noncommuting variables. SIAM J. Optim. 20(5), 2157\u20132180 (2010). https:\/\/doi.org\/10.1137\/090760155","journal-title":"SIAM J. Optim."},{"issue":"5","key":"301_CR34","doi-asserted-by":"publisher","first-page":"2157","DOI":"10.1137\/090760155","volume":"20","author":"S Pironio","year":"2010","unstructured":"Pironio, S., Navascu\u00e9s, M., Acin, A.: Convergent relaxations of polynomial optimization problems with noncommuting variables. SIAM J. Optim. 20(5), 2157\u20132180 (2010)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"301_CR35","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1512\/iumj.1993.42.42045","volume":"42","author":"M Putinar","year":"1993","unstructured":"Putinar, M.: Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42(3), 969\u2013984 (1993). https:\/\/doi.org\/10.1512\/iumj.1993.42.42045","journal-title":"Indiana Univ. Math. J."},{"issue":"2","key":"301_CR36","first-page":"363","volume":"45","author":"B Reznick","year":"1978","unstructured":"Reznick, B., et al.: Extremal PSD forms with few terms. Duke Math. Jo. 45(2), 363\u2013374 (1978)","journal-title":"Duke Math. Jo."},{"key":"301_CR37","volume-title":"A Unified Algebraic Approach to Control Design","author":"RE Skelton","year":"1997","unstructured":"Skelton, R.E., Iwasaki, T., Grigoriadis, D.E.: A Unified Algebraic Approach to Control Design. CRC Press, Boca Raton (1997)"},{"key":"301_CR38","doi-asserted-by":"crossref","unstructured":"Tacchi, M., Weisser, T., Lasserre, J.B., Henrion, D.: Exploiting sparsity for semi-algebraic set volume computation. Foundations of Computational Mathematics pp. 1\u201349 (2021)","DOI":"10.1007\/s10208-021-09508-w"},{"key":"301_CR39","doi-asserted-by":"publisher","unstructured":"Takesaki, M.: Theory of operator algebras. III, Encyclopaedia of Mathematical Sciences, vol. 127. Springer-Verlag, Berlin (2003). https:\/\/doi.org\/10.1007\/978-3-662-10453-8. Operator Algebras and Non-commutative Geometry, 8","DOI":"10.1007\/978-3-662-10453-8"},{"issue":"4","key":"301_CR40","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1561\/2400000006","volume":"1","author":"L Vandenberghe","year":"2015","unstructured":"Vandenberghe, L., Andersen, M.S., et al.: Chordal graphs and semidefinite optimization. Found. Trends Regist. Optim. 1(4), 241\u2013433 (2015)","journal-title":"Found. Trends Regist. Optim."},{"issue":"1","key":"301_CR41","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 programming relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim. 17(1), 218\u2013242 (2006)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"301_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1377612.1377619","volume":"35","author":"H Waki","year":"2008","unstructured":"Waki, H., Kim, S., Kojima, M., Muramatsu, M., Sugimoto, H.: Algorithm 883: SparsePOP: a sparse semidefinite programming relaxation of polynomial optimization problems. ACM Trans. Math. Softw. 35(2), 1\u201313 (2008)","journal-title":"ACM Trans. Math. Softw."},{"key":"301_CR43","unstructured":"Wang, J.: ChordalGraph: A Julia package to handle chordal graphs (2020). https:\/\/github.com\/wangjie212\/ChordalGraph"},{"key":"301_CR44","doi-asserted-by":"crossref","unstructured":"Wang, J., Li, H., Xia, B.: A new sparse SOS decomposition algorithm based on term sparsity. In: Proceedings of the 2019 on international symposium on symbolic and algebraic computation, pp. 347\u2013354 (2019)","DOI":"10.1145\/3326229.3326254"},{"key":"301_CR45","doi-asserted-by":"crossref","unstructured":"Wang, J., Maggio, M., Magron, V.: SparseJSR: A fast algorithm to compute joint spectral radius via sparse SOS decompositions. In: 2021 American Control Conference. IEEE (2021)","DOI":"10.23919\/ACC50511.2021.9483347"},{"issue":"1","key":"301_CR46","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":"1","key":"301_CR47","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."},{"key":"301_CR48","unstructured":"Wang, J., Magron, V., Lasserre, J.B., Mai, N.H.A.: CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization. arXiv:2005.02828 (2020)"},{"issue":"1","key":"301_CR49","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1137\/19M1305045","volume":"3","author":"A Yurtsever","year":"2021","unstructured":"Yurtsever, A., Tropp, J.A., Fercoq, O., Udell, M., Cevher, V.: Scalable semidefinite programming. SIAM J. Math. Data Sci. 3(1), 171\u2013200 (2021)","journal-title":"SIAM J. Math. Data Sci."},{"key":"301_CR50","unstructured":"Zhou, Q., Marecek, J.: Proper learning of linear dynamical systems as a non-commutative polynomial optimisation problem. arXiv preprint arXiv:2002.01444 (2020)"},{"key":"301_CR51","unstructured":"Zhou, Q., Marecek, J., Shorten, R.N.: Fairness in forecasting and learning linear dynamical systems. arXiv preprint arXiv:2006.07315 (2020)"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-021-00301-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-021-00301-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-021-00301-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,23]],"date-time":"2021-09-23T12:43:12Z","timestamp":1632400992000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-021-00301-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,27]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["301"],"URL":"https:\/\/doi.org\/10.1007\/s10589-021-00301-7","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,27]]},"assertion":[{"value":"15 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 July 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 July 2021","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 that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}