{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:41:05Z","timestamp":1787341265064,"version":"build-2736575974"},"reference-count":56,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2023YFA1009401"],"award-info":[{"award-number":["2023YFA1009401"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002367","name":"Chinese Academy of Sciences","doi-asserted-by":"publisher","award":["XDB0640000"],"award-info":[{"award-number":["XDB0640000"]}],"id":[{"id":"10.13039\/501100002367","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002367","name":"Chinese Academy of Sciences","doi-asserted-by":"publisher","award":["XDB0640200"],"award-info":[{"award-number":["XDB0640200"]}],"id":[{"id":"10.13039\/501100002367","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12201618"],"award-info":[{"award-number":["12201618"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12171324"],"award-info":[{"award-number":["12171324"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12471478"],"award-info":[{"award-number":["12471478"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["51NF40 180545"],"award-info":[{"award-number":["51NF40 180545"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>A polynomial matrix inequality (PMI) is a formula asserting that a polynomial matrix is positive semidefinite. Polynomial matrix optimization (PMO) concerns minimizing the smallest eigenvalue of a symmetric polynomial matrix subject to a tuple of PMIs. This work explores the use of sparsity methods in reducing the complexity of sum of squares\u2013based methods in verifying PMIs or solving PMO. In the unconstrained setting, Newton polytopes can be employed to sparsify the monomial basis, resulting in smaller semidefinite programs. In the general setting, we show how to exploit different types of sparsity (term sparsity, correlative sparsity, matrix sparsity) encoded in polynomial matrices to derive sparse semidefinite programming relaxations for PMO. For term sparsity, we show that the block structures of the term sparsity iterations with maximal chordal extensions converge to the one determined by PMI sign symmetries. For correlative sparsity, unlike the scalar case, we provide a counterexample showing that asymptotic convergence does not hold under the Archimedean condition and the running intersection property. By employing the theory of matrix-valued measures, we establish several results on detecting global optimality and retrieving optimal solutions under correlative sparsity. The effectiveness of sparsity methods on reducing computational complexity is demonstrated on various examples of PMO.<\/jats:p>","DOI":"10.1137\/24m1719761","type":"journal-article","created":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T07:06:26Z","timestamp":1775027186000},"page":"503-533","source":"Crossref","is-referenced-by-count":0,"title":["Sparse Polynomial Matrix Optimization"],"prefix":"10.1137","volume":"36","author":[{"given":"Jared","family":"Miller","sequence":"first","affiliation":[{"name":"Automatic Control Laboratory (IfA), Department of Information Technology and Electrical Engineering (D-ITET), ETH Z\u00fcrich, 8092, Z\u00fcrich, Switzerland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9681-1451","authenticated-orcid":true,"given":"Jie","family":"Wang","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3106-2653","authenticated-orcid":true,"given":"Feng","family":"Guo","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, Liaoning Province, China."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,4,1]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ifacol.2024.08.515"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(88)90240-6"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3216-0_8"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01877-6"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02771790"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972290"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.03.008"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/140988978"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-011-0056-y"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/22M1484511"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"S. Gao, S. Kong, and E. M. Clarke, dReal: An SMT solver for nonlinear theories over the reals, in International Conference on Automated Deduction, Springer, 2013, pp. 208\u2013214.","DOI":"10.1007\/978-3-642-38574-2_14"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2003.12.011"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s00013-007-2234-z"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(84)90207-6"},{"key":"ref15","first-page":"1734","volume":"50","author":"Guo F.","year":"2025","journal-title":"A moment-sum-of-squares hierarchy for robust polynomial matrix inequality optimization with sum-of-squares convexity"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"F. Guo, J. Wang, and J. Zheng, Exploiting sign symmetries in minimizing sums of rational functions, online in Math. Oper. Res. (2025).","DOI":"10.1287\/moor.2024.0541"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s11081-025-10000-5"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.2307\/3597203"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20155"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2005.863494"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2011.2178717"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.3182\/20050703-6-CZ-1902.01020"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-025-02199-z"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1186\/s40687-016-0052-2"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0402-6"},{"key":"ref26","volume-title":"Sums of Squares Relaxations of Polynomial Semidefinite Programs","author":"Kojima M.","year":"2003"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-007-9112-2"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/05064504X"},{"key":"ref29","series-title":"Imp. Coll. Press Optim. Ser. 1","volume-title":"Moments, Positive Polynomials and Their Applications","author":"Lasserre J. B.","year":"2010"},{"key":"ref30","volume-title":"Block Diagonalization of Matrix-Valued Sum-of-Squares Programs","author":"L\u00f6fberg J.","year":"2008"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2009.2017144"},{"key":"ref32","unstructured":"V. Magron and J. Wang, TSSOS: A Julia library to exploit sparsity for large-scale polynomial optimization, in The Sixteenth Effective Methods in Algebraic Geometry Conference, 2021."},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2022.08.002"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1142\/q0382"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2025.3545766"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346336"},{"key":"ref37","doi-asserted-by":"crossref","unstructured":"K. G. Murty and S. N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, 9 (1987), pp. 117\u2013129.","DOI":"10.1007\/BF02592948"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0498"},{"key":"ref39","first-page":"1","author":"Nie J.","year":"2026","journal-title":"J. Glob. Optim."},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2006.07.002"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2014.2350171"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1007\/10997703_11"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1512\/iumj.1993.42.42045"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.5802\/alco.5"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-78-04519-2"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0684-2"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1007\/s00158-021-02957-5"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1137\/050623802"},{"key":"ref49","doi-asserted-by":"crossref","unstructured":"J. Wang and V. Magron, A second order cone characterization for sums of nonnegative circuits, in Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation, ACM, 2020, pp. 450\u2013457.","DOI":"10.1145\/3373207.3404033"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-021-00301-7"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-021-01975-z"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1137\/20M1323564"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1137\/19M1307871"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1145\/3569709"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01728-w"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1016\/j.arcontrol.2021.09.001"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1719761","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:11:46Z","timestamp":1787339506000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1719761"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,1]]},"references-count":56,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1137\/24M1719761"],"URL":"https:\/\/doi.org\/10.1137\/24m1719761","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,1]]}}}