{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T18:57:20Z","timestamp":1775069840099,"version":"3.50.1"},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T00:00:00Z","timestamp":1637366400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T00:00:00Z","timestamp":1637366400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Clarendon Scholarship"},{"name":"AFOSR Young Investigator Program"},{"name":"Imperial College Research Fellowship"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,1]]},"abstract":"Abstract<\/jats:title>We prove decomposition theorems for sparse positive (semi)definite polynomial matrices that can be viewed as sparsity-exploiting versions of the Hilbert\u2013Artin, Reznick, Putinar, and Putinar\u2013Vasilescu Positivstellens\u00e4tze. First, we establish that a polynomial matrix P<\/jats:italic>(x<\/jats:italic>) with chordal sparsity is positive semidefinite for all $$x\\in \\mathbb {R}^n$$<\/jats:tex-math>\n \n x<\/mml:mi>\n \u2208<\/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> if and only if there exists a sum-of-squares (SOS) polynomial $$\\sigma (x)$$<\/jats:tex-math>\n \n \u03c3<\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that $$\\sigma P$$<\/jats:tex-math>\n \n \u03c3<\/mml:mi>\n P<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a sum of sparse SOS matrices. Second, we show that setting $$\\sigma (x)=(x_1^2 + \\cdots + x_n^2)^\\nu $$<\/jats:tex-math>\n \n \u03c3<\/mml:mi>\n \n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \n \n (<\/mml:mo>\n \n x<\/mml:mi>\n 1<\/mml:mn>\n 2<\/mml:mn>\n <\/mml:msubsup>\n +<\/mml:mo>\n \u22ef<\/mml:mo>\n +<\/mml:mo>\n \n x<\/mml:mi>\n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msubsup>\n )<\/mml:mo>\n <\/mml:mrow>\n \u03bd<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for some integer $$\\nu $$<\/jats:tex-math>\n \u03bd<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> suffices if P<\/jats:italic> is homogeneous and positive definite globally. Third, we prove that if P<\/jats:italic> is positive definite on a compact semialgebraic set $$\\mathcal {K}=\\{x:g_1(x)\\ge 0,\\ldots ,g_m(x)\\ge 0\\}$$<\/jats:tex-math>\n \n K<\/mml:mi>\n =<\/mml:mo>\n {<\/mml:mo>\n x<\/mml:mi>\n :<\/mml:mo>\n \n g<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n \n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n \n g<\/mml:mi>\n m<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n 0<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> satisfying the Archimedean condition, then $$P(x) = S_0(x) + g_1(x)S_1(x) + \\cdots + g_m(x)S_m(x)$$<\/jats:tex-math>\n \n P<\/mml:mi>\n \n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \n S<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msub>\n \n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n \n g<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n \n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n S<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n \n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n \u22ef<\/mml:mo>\n +<\/mml:mo>\n \n g<\/mml:mi>\n m<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n S<\/mml:mi>\n m<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for matrices $$S_i(x)$$<\/jats:tex-math>\n \n \n S<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> that are sums of sparse SOS matrices. Finally, if $$\\mathcal {K}$$<\/jats:tex-math>\n K<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is not compact or does not satisfy the Archimedean condition, we obtain a similar decomposition for $$(x_1^2 + \\cdots + x_n^2)^\\nu P(x)$$<\/jats:tex-math>\n \n \n \n (<\/mml:mo>\n \n x<\/mml:mi>\n 1<\/mml:mn>\n 2<\/mml:mn>\n <\/mml:msubsup>\n +<\/mml:mo>\n \u22ef<\/mml:mo>\n +<\/mml:mo>\n \n x<\/mml:mi>\n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msubsup>\n )<\/mml:mo>\n <\/mml:mrow>\n \u03bd<\/mml:mi>\n <\/mml:msup>\n P<\/mml:mi>\n \n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with some integer $$\\nu \\ge 0$$<\/jats:tex-math>\n \n \u03bd<\/mml:mi>\n \u2265<\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> when P<\/jats:italic> and $$g_1,\\ldots ,g_m$$<\/jats:tex-math>\n \n \n g<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n \n g<\/mml:mi>\n m<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are homogeneous of even degree. Using these results, we find sparse SOS representation theorems for polynomials that are quadratic and correlatively sparse in a subset of variables, and we construct new convergent hierarchies of sparsity-exploiting SOS reformulations for convex optimization problems with large and sparse polynomial matrix inequalities. Numerical examples demonstrate that these hierarchies can have a significantly lower computational complexity than traditional ones.<\/jats:p>","DOI":"10.1007\/s10107-021-01728-w","type":"journal-article","created":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T11:02:28Z","timestamp":1637406148000},"page":"71-108","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Sum-of-squares chordal decomposition of polynomial matrix inequalities"],"prefix":"10.1007","volume":"197","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1545-231X","authenticated-orcid":false,"given":"Yang","family":"Zheng","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0808-0944","authenticated-orcid":false,"given":"Giovanni","family":"Fantuzzi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,20]]},"reference":[{"key":"1728_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":"1728_CR2","doi-asserted-by":"publisher","unstructured":"Andersen, E.D., Andersen, K.D.: The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm. In: High Performance Optimization, pp. 197\u2013232. Springer (2000). https:\/\/doi.org\/10.1007\/978-1-4757-3216-0_8","DOI":"10.1007\/978-1-4757-3216-0_8"},{"issue":"4","key":"1728_CR3","doi-asserted-by":"publisher","first-page":"1855","DOI":"10.1109\/TPWRS.2013.2294479","volume":"29","author":"MS Andersen","year":"2014","unstructured":"Andersen, M.S., Hansson, A., Vandenberghe, L.: Reduced-complexity semidefinite relaxations of optimal power flow problems. IEEE Trans. Power Syst. 29(4), 1855\u20131863 (2014)","journal-title":"IEEE Trans. Power Syst."},{"issue":"8","key":"1728_CR4","doi-asserted-by":"publisher","first-page":"2151","DOI":"10.1109\/TAC.2014.2305934","volume":"59","author":"MS Andersen","year":"2014","unstructured":"Andersen, M.S., Pakazad, S.K., Hansson, A., Rantzer, A.: Robust stability analysis of sparsely interconnected uncertain systems. IEEE Trans. Autom. Control 59(8), 2151\u20132156 (2014)","journal-title":"IEEE Trans. Autom. Control"},{"issue":"1","key":"1728_CR5","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/BF02952513","volume":"5","author":"E Artin","year":"1927","unstructured":"Artin, E.: \u00dcber die Zerlegung definiter Funktionen in Quadrate. Abh. Math. Semin. Univ. Hambg. 5(1), 100\u2013115 (1927)","journal-title":"Abh. Math. Semin. Univ. Hambg."},{"key":"1728_CR6","doi-asserted-by":"crossref","unstructured":"Aylward, E.M., Itani, S.M., Parrilo, P.A.: Explicit SOS decompositions of univariate polynomial matrices and the Kalman\u2013Yakubovich\u2013Popov lemma. In: Proceedings of the 46th IEEE Conference on Decision and Control, pp. 5660\u20135665 (2007)","DOI":"10.1109\/CDC.2007.4435026"},{"key":"1728_CR7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"issue":"11","key":"1728_CR8","doi-asserted-by":"publisher","first-page":"2500","DOI":"10.1109\/TAC.2010.2046926","volume":"55","author":"G Chesi","year":"2010","unstructured":"Chesi, G.: LMI techniques for optimization over polynomials in control: a survey. IEEE Trans. Autom. Control 55(11), 2500\u20132510 (2010)","journal-title":"IEEE Trans. Autom. Control"},{"key":"1728_CR9","doi-asserted-by":"crossref","unstructured":"Dinh, T.H., Ho, M.T., Le, C.T.: Positivstellens\u00e4tze for polynomial matrices. Positivity (2021)","DOI":"10.1007\/s11117-021-00816-7"},{"issue":"2","key":"1728_CR10","first-page":"171","volume":"19","author":"THB Du","year":"2017","unstructured":"Du, T.H.B.: A note on Positivstellens\u00e4tze for matrix polynomials. East-West J. Math. 19(2), 171\u2013182 (2017)","journal-title":"East-West J. Math."},{"issue":"3","key":"1728_CR11","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1137\/S1052623400366218","volume":"11","author":"M Fukuda","year":"2001","unstructured":"Fukuda, M., Kojima, M., Murota, K., Nakata, K.: Exploiting sparsity in semidefinite programming via matrix completion I: general framework. SIAM J. Optim. 11(3), 647\u2013674 (2001)","journal-title":"SIAM J. Optim."},{"issue":"1\u20133","key":"1728_CR12","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.jpaa.2003.12.011","volume":"192","author":"K Gatermann","year":"2004","unstructured":"Gatermann, K., Parrilo, P.A.: Symmetry groups, semidefinite programs, and sums of squares. J. Pure Appl. Algebra 192(1\u20133), 95\u2013128 (2004)","journal-title":"J. Pure Appl. Algebra"},{"issue":"5","key":"1728_CR13","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s00013-007-2234-z","volume":"89","author":"D Grimm","year":"2007","unstructured":"Grimm, D., Netzer, T., Schweighofer, M.: A note on the representation of positive polynomials with structured sparsity. Arch. Math. (Basel) 89(5), 399\u2013403 (2007)","journal-title":"Arch. Math. (Basel)"},{"issue":"6","key":"1728_CR14","doi-asserted-by":"publisher","first-page":"1456","DOI":"10.1109\/TAC.2011.2178717","volume":"57","author":"D Henrion","year":"2011","unstructured":"Henrion, D., Lasserre, J.B.: Inner approximations for polynomial matrix inequalities and robust stability regions. IEEE Trans. Autom. Control 57(6), 1456\u20131467 (2011)","journal-title":"IEEE Trans. Autom. Control"},{"issue":"2","key":"1728_CR15","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."},{"issue":"4","key":"1728_CR16","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1016\/j.laa.2010.04.012","volume":"433","author":"N Kakimura","year":"2010","unstructured":"Kakimura, N.: A direct proof for the matrix decomposition of chordal-structured positive semidefinite matrices. Linear Algebra Appl. 433(4), 819\u2013823 (2010)","journal-title":"Linear Algebra Appl."},{"key":"1728_CR17","first-page":"1","volume":"01","author":"I Klep","year":"2021","unstructured":"Klep, I., Magron, V., Povh, J.: Sparse noncommutative polynomial optimization. Math. Program. 01, 1\u201337 (2021)","journal-title":"Math. Program."},{"key":"1728_CR18","unstructured":"Kojima, M.: Sums of squares relaxations of polynomial semidefinite programs. In: Research Reports on Mathematical and Computing Sciences Series B: Operations Research B-397. Tokyo Institute of Technology (2003)"},{"issue":"3","key":"1728_CR19","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":"1728_CR20","volume-title":"Moments, Positive Polynomials and Their Applications","author":"JB Lasserre","year":"2010","unstructured":"Lasserre, J.B.: Moments, Positive Polynomials and Their Applications. Imperial College Press, London (2010)"},{"key":"1728_CR21","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)"},{"key":"1728_CR22","first-page":"157","volume-title":"Emerging Applications of Algebraic Geometry, The IMA Volumes in Mathematics and its Applications","author":"M Laurent","year":"2009","unstructured":"Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Putinar, M., Sullivant, S. (eds.) Emerging Applications of Algebraic Geometry, The IMA Volumes in Mathematics and its Applications, pp. 157\u2013270. Springer, New York (2009)"},{"key":"1728_CR23","unstructured":"L\u00f6fberg, J.: YALMIP: a toolbox for modeling and optimization in MATLAB. In: Proceedings of the IEEE International Symposium on Computer-Aided Control System Design, pp. 284\u2013289 (2004)"},{"issue":"5","key":"1728_CR24","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1109\/TAC.2009.2017144","volume":"54","author":"J L\u00f6fberg","year":"2009","unstructured":"L\u00f6fberg, J.: Pre-and post-processing sum-of-squares programs in practice. IEEE Trans. Autom. Control 54(5), 1007\u20131011 (2009)","journal-title":"IEEE Trans. Autom. Control"},{"key":"1728_CR25","unstructured":"Mai, N.H.A., Magron, V., Lasserre, J.B.: A sparse version of Reznick\u2019s Positivstellensatz. arXiv:2002.05101 [math.OC] (2020)"},{"key":"1728_CR26","unstructured":"Mason, R.: A Chordal Sparsity Approach to Scalable Linear and Nonlinear Systems Analysis. Ph.D. thesis, University of Oxford (2015)"},{"issue":"4","key":"1728_CR27","doi-asserted-by":"publisher","first-page":"3987","DOI":"10.1109\/TPWRS.2013.2258044","volume":"28","author":"DK Molzahn","year":"2013","unstructured":"Molzahn, D.K., Holzer, J.T., Lesieutre, B.C., DeMarco, C.L.: Implementation of a large-scale optimal power flow solver based on semidefinite programming. IEEE Trans. Power Syst. 28(4), 3987\u20133998 (2013)","journal-title":"IEEE Trans. Power Syst."},{"key":"1728_CR28","unstructured":"Motzkin, T.S.: The arithmetic-geometric inequality. In: Inequalities (Proceedings of a Symposium Held at Wright-Patterson Air Force Base, Ohio, 1965), pp. 205\u2013224 (1967)"},{"issue":"2","key":"1728_CR29","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"KG Murty","year":"1987","unstructured":"Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39(2), 117\u2013129 (1987)","journal-title":"Math. Program."},{"issue":"2","key":"1728_CR30","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s10107-002-0351-9","volume":"95","author":"K Nakata","year":"2003","unstructured":"Nakata, K., Fujisawa, K., Fukuda, M., Kojima, M., Murota, K.: Exploiting sparsity in semidefinite programming via matrix completion II: implementation and numerical results. Math. Program. B 95(2), 303\u2013327 (2003)","journal-title":"Math. Program. B"},{"key":"1728_CR31","doi-asserted-by":"crossref","unstructured":"Nemirovski, A.: Advances in convex optimization: conic programming. In: International Congress of Mathematicians, vol.\u00a01, pp. 413\u2013444 (2006)","DOI":"10.4171\/022-1\/17"},{"key":"1728_CR32","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970791","volume-title":"Interior-Point Polynomial Algorithms in Convex Programming","author":"Y Nesterov","year":"1994","unstructured":"Nesterov, Y., Nemirovski, A.: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia (1994)"},{"issue":"4","key":"1728_CR33","doi-asserted-by":"publisher","first-page":"1534","DOI":"10.1137\/060668791","volume":"19","author":"J Nie","year":"2008","unstructured":"Nie, J., Demmel, J.: Sparse SOS relaxations for minimizing functions that are summations of small polynomials. SIAM J. Optim. 19(4), 1534\u20131558 (2008)","journal-title":"SIAM J. Optim."},{"key":"1728_CR34","first-page":"47","volume-title":"Semidefinite Optimization and Convex Algebraic Geometry, Chap. 3","author":"PA Parrilo","year":"2013","unstructured":"Parrilo, P.A.: Polynomial optimization, sums of squares and applications. In: Blekherman, G., Parrilo, P.A., Thomas, R.R. (eds.) Semidefinite Optimization and Convex Algebraic Geometry, Chap. 3, 1st edn., pp. 47\u2013157. SIAM, Philadelphia (2013)","edition":"1"},{"key":"1728_CR35","doi-asserted-by":"crossref","unstructured":"Permenter, F., Parrilo, P.A.: Basis selection for SOS programs via facial reduction and polyhedral approximations. In: Proceedings of the 53rd IEEE Conference on Decision and Control, pp. 6615\u20136620 (2014)","DOI":"10.1109\/CDC.2014.7040427"},{"issue":"3","key":"1728_CR36","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)","journal-title":"Indiana Univ. Math. J."},{"issue":"7","key":"1728_CR37","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1016\/S0764-4442(99)80251-1","volume":"328","author":"M Putinar","year":"1999","unstructured":"Putinar, M., Vasilescu, F.H.: Positive polynomials on semi-algebraic sets. C. R. Math. Acad. Sci. Paris 328(7), 585\u2013589 (1999)","journal-title":"C. R. Math. Acad. Sci. Paris"},{"issue":"2","key":"1728_CR38","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1215\/S0012-7094-78-04519-2","volume":"45","author":"B Reznick","year":"1978","unstructured":"Reznick, B.: Extremal PSD forms with few terms. Duke Math. J. 45(2), 363\u2013374 (1978)","journal-title":"Duke Math. J."},{"key":"1728_CR39","doi-asserted-by":"crossref","unstructured":"Reznick, B.: Uniform denominators in Hilbert\u2019s seventeenth problem. Math. Z. 220, 75\u201397 (1995)","DOI":"10.1007\/BF02572604"},{"issue":"1","key":"1728_CR40","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1287\/moor.1120.0558","volume":"38","author":"C Riener","year":"2013","unstructured":"Riener, C., Theobald, T., Andr\u00e9n, L.J., Lasserre, J.B.: Exploiting symmetries in SDP-relaxations for polynomial optimization. Math. Oper. Res. 38(1), 122\u2013141 (2013)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"1728_CR41","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1016\/0022-247X(70)90282-9","volume":"32","author":"DJ Rose","year":"1970","unstructured":"Rose, D.J.: Triangulated graphs and the elimination process. J. Math. Anal. Appl 32(3), 597\u2013609 (1970)","journal-title":"J. Math. Anal. Appl"},{"key":"1728_CR42","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10107-005-0684-2","volume":"107","author":"C Scherer","year":"2006","unstructured":"Scherer, C., Hol, C.: Matrix sum-of-squares relaxations for robust semi-definite programs. Math. Program. 107, 189\u2013211 (2006)","journal-title":"Math. Program."},{"issue":"1","key":"1728_CR43","doi-asserted-by":"publisher","first-page":"3","DOI":"10.3166\/ejc.12.3-29","volume":"12","author":"CW Scherer","year":"2006","unstructured":"Scherer, C.W.: LMI relaxations in robust control. Eur. J. Control 12(1), 3\u201329 (2006)","journal-title":"Eur. J. Control"},{"key":"1728_CR44","doi-asserted-by":"publisher","unstructured":"Schm\u00fcdgen, K.: Noncommutative real algebraic geometry some basic concepts and first ideas. In: Putinar, M., Sullivant, S. (eds.) Emerging Applications of Algebraic Geometry, pp. 325\u2013350. Springer, New York (2009). https:\/\/doi.org\/10.1007\/978-0-387-09686-5_9","DOI":"10.1007\/978-0-387-09686-5_9"},{"issue":"2","key":"1728_CR45","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/130926924","volume":"24","author":"Y Sun","year":"2014","unstructured":"Sun, Y., Andersen, M.S., Vandenberghe, L.: Decomposition in conic optimization with partially separable structure. SIAM J. Optim. 24(2), 873\u2013897 (2014)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"1728_CR46","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 Optim. 1(4), 241\u2013433 (2015)","journal-title":"Found. Trends Optim."},{"issue":"1","key":"1728_CR47","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1137\/1038003","volume":"38","author":"L Vandenberghe","year":"1996","unstructured":"Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38(1), 49\u201395 (1996)","journal-title":"SIAM Rev."},{"issue":"1","key":"1728_CR48","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."},{"key":"1728_CR49","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 International Symposium on Symbolic and Algebraic Computation, ISSAC pp. 347\u2013354 (2019)","DOI":"10.1145\/3326229.3326254"},{"issue":"1","key":"1728_CR50","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":"1728_CR51","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":"1728_CR52","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 [math.OC] (2020)"},{"key":"1728_CR53","doi-asserted-by":"crossref","unstructured":"Zheng, Y., Fantuzzi, G., Papachristodoulou, A.: Decomposition and completion of sum-of-squares matrices. In: Proceedings of the 57th IEEE Conference on Decision and Control, pp. 4026\u20134031 (2018)","DOI":"10.1109\/CDC.2018.8619144"},{"key":"1728_CR54","doi-asserted-by":"crossref","unstructured":"Zheng, Y., Fantuzzi, G., Papachristodoulou, A.: Sparse sum-of-squares (SOS) optimization: a bridge between DSOS\/SDSOS and SOS optimization for sparse polynomials. In: Proceedings of the 2019 American Control Conference, pp. 5513\u20135518 (2019)","DOI":"10.23919\/ACC.2019.8814998"},{"key":"1728_CR55","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/s10107-019-01366-3","volume":"180","author":"Y Zheng","year":"2020","unstructured":"Zheng, Y., Fantuzzi, G., Papachristodoulou, A., Goulart, P., Wynn, A.: Chordal decomposition in operator-splitting methods for sparse semidefinite programs. Math. Program. 180, 489\u2013532 (2020)","journal-title":"Math. Program."},{"issue":"3","key":"1728_CR56","doi-asserted-by":"publisher","first-page":"752","DOI":"10.1109\/TAC.2017.2726578","volume":"63","author":"Y Zheng","year":"2018","unstructured":"Zheng, Y., Mason, R.P., Papachristodoulou, A.: Scalable design of structured controllers using chordal decomposition. IEEE Trans. Autom. Control 63(3), 752\u2013767 (2018)","journal-title":"IEEE Trans. Autom. Control"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01728-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01728-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01728-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,22]],"date-time":"2023-01-22T01:06:00Z","timestamp":1674349560000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01728-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,20]]},"references-count":56,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["1728"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01728-w","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,20]]},"assertion":[{"value":"6 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}