{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:23:10Z","timestamp":1787340190439,"version":"build-2736575974"},"reference-count":58,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>This paper studies the complexity of matrix Putinar\u2019s Positivstellens\u00e4tz on the semialgebraic set that is given by the polynomial matrix inequality. When the quadratic module generated by the constrained polynomial matrix is Archimedean, we prove a polynomial bound on the degrees of terms appearing in the representation of matrix Putinar\u2019s Positivstellens\u00e4tz. Estimates on the exponent and constant are given. As a byproduct, a polynomial bound on the convergence rate of matrix sum-of-squares relaxations is obtained, which resolves an open question raised by Dinh and Pham [ J. Complexity, 41 (2017), pp. 58\u201371]. When the constraining set is unbounded, we also prove a similar bound for the matrix version of Putinar\u2013Vasilescu\u2019s Positivstellens\u00e4tz by exploiting homogenization techniques.<\/jats:p>","DOI":"10.1137\/24m1675461","type":"journal-article","created":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T04:00:40Z","timestamp":1741838440000},"page":"567-591","source":"Crossref","is-referenced-by-count":5,"title":["On the Complexity of Matrix Putinar\u2019s Positivstellens\u00e4tz"],"prefix":"10.1137","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9734-5387","authenticated-orcid":true,"given":"Lei","family":"Huang","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of California San Diego, La Jolla, CA 92093 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,3,13]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1137\/22M1540818"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01877-6"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2024.08.022"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1137\/23M1555430"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03718-8"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2010.2046926"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2012.03.011"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/100814147"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1142\/S0129167X16500129"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2016.11.007"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s11117-021-00816-7"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01537-7"},{"key":"ref13","series-title":"Morgan Kaufmann Ser. Comput. Graph. Geom. Model.","volume-title":"Curves and Surfaces for CAGD: A Practical Guide","author":"Farin G.","year":"2021","edition":"5"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1142\/q0066"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-008-0240-y"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2005.863494"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2011.2178717"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1142\/q0252"},{"key":"ref19","unstructured":"X. Hu, I. Klep, and J. Nie, Positivstellens\u00e4tze and Moment Problems with Universal Quantifiers, preprint, https:\/\/arxiv.org\/abs\/2401.12359, 2024."},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-022-01940-3"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01878-5"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-023-02139-z"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1137\/23M1605430"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"L. Huang, J. Nie and Y. Yuan, Finite convergence of the Moment-SOS hierarchy for polynomial matrix optimization, Math. Program. (2025), to appear.","DOI":"10.1007\/s10107-025-02199-z"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2009.2017159"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1515\/crll.2001.023"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1512\/iumj.2010.59.4107"},{"key":"ref28","volume-title":"Research Reports on Mathematical and Computing Sciences Series B: Operations Research B-397","author":"Kojima M.","year":"2003"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-024-02071-6"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1006\/jath.1998.3314"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1137\/080728214"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-09686-5_7"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.4064\/sm-18-1-87-136"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2022.101663"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.5802\/afst.1131"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0680-x"},{"key":"ref38","doi-asserted-by":"crossref","unstructured":"J. Nie, Moment and Polynomial Optimization, SIAM, Philadelphia, 2023, https:\/\/doi.org\/10.1137\/1.9781611977608.","DOI":"10.1137\/1.9781611977608"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2006.07.002"},{"key":"ref40","first-page":"141","volume":"73","author":"Polya G.","year":"1928","journal-title":"Vierteljahresschrift der Naturforschenden Gesellschaft in Zurich"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(00)00155-9"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1512\/iumj.1993.42.42045"},{"key":"ref43","first-page":"585","volume":"328","author":"Putinar M.","year":"1999","journal-title":"C. R. Acad. Sci. Ser. I Math."},{"key":"ref44","first-page":"495","volume":"328","author":"Putinar M.","year":"1999","journal-title":"C. R. Acad. Sci. Ser. I Math."},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1137\/0713043"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2005.01.043"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.3166\/ejc.12.3-29"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0684-2"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1007\/BF01446568"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-09686-5_9"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2004.01.005"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614439"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1137\/21M1458338"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-022-01922-5"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01745-9"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1060.0195"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1007\/s00158-021-02957-5"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01728-w"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1675461","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:23:35Z","timestamp":1787336615000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1675461"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,13]]},"references-count":58,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1137\/24M1675461"],"URL":"https:\/\/doi.org\/10.1137\/24m1675461","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,13]]}}}