{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T14:19:03Z","timestamp":1790518743451,"version":"4.1.0"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>This paper discusses how to find the global minimum of functions that are summations of small polynomials (\u201csmall\u201d means involving a small number of variables). Some sparse sum of squares (SOS) techniques are proposed. We compare their computational complexity and lower bounds with prior SOS relaxations. Under certain conditions, we also discuss how to extract the global minimizers from these sparse relaxations. The proposed methods are especially useful in solving sparse polynomial system and nonlinear least squares problems. Numerical experiments are presented which show that the proposed methods significantly improve the computational performance of prior methods for solving these problems. Lastly, we present applications of this sparsity technique in solving polynomial systems derived from nonlinear differential equations and sensor network localization.<\/jats:p>","DOI":"10.1137\/060668791","type":"journal-article","created":{"date-parts":[[2008,12,31]],"date-time":"2008-12-31T19:21:26Z","timestamp":1230751286000},"page":"1534-1558","source":"Crossref","is-referenced-by-count":37,"title":["Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials"],"prefix":"10.1137","volume":"19","author":[{"given":"Jiawang","family":"Nie","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Demmel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,12,31]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"A.L. Allgower, D.J. Bates, A.J. Sommese, and C.W. Wampler,\n                      Solution of polynomial systems derived from differential equations\n                      , Computing, 76 (2005), pp, 1\u201310.","DOI":"10.1007\/s00607-005-0132-4"},{"key":"R2","unstructured":"S.J. Benson and Y. Ye,\n                      DSDP3: Dual scaling algorithm for general positive semidefinite programming\n                      , Technical report ANL\/MCS-P851-1000, Mathematics and Computer Science Division, Argonne National Laboratory, 2001."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"J. Blair and B. Peyton,\n                      An introduction to chordal graphs and clique trees\n                      , in Graph Theory and Sparse Matrix Computations, J. George, J. Gilbert, and J. Liu, eds., Springer Verlag, New York, 1993, pp. 1\u201330.","DOI":"10.1007\/978-1-4613-8369-7_1"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/BF02771790"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2006.877401"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1988-0929544-3"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-00-02472-7"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2003.12.011"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"D. Henrion and J. Lasserre,\n                      Detecting global optimality and extracting solutions in GloptiPoly\n                      , in Positive Polynomials in Control, D. Henrion and A. Garulli, eds., Lecture Notes on Control and Information Sciences, Springer Verlag, New York, 2005.","DOI":"10.1007\/10997703_15"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/04060562X"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/030601260"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0554-3"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/04061413X"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/05064504X"},{"key":"R16","unstructured":"M. Laurent,\n                      Moment matrices and optimization over polynomials - A survey on selected topics\n                      , Emerging Applications of Algebraic Geometry, IMA Volumes in Mathematics and its Applications 149, (des. M. Putinar and S. Sullivant), Springer, to appear."},{"key":"R17","unstructured":"J. L\u00f6fberg,\n                      YALMIP: A toolbox for Modeling and Optimization in MATLAB\n                      , in Proceedings of the CACSD Conference, Taipei, Taiwan, 2004. http:\/\/control.ee.ethz.ch\/~joloef\/yalmip.php."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/355934.355936"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/0721052"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0672-6"},{"key":"R21","unstructured":"J. Nie,\n                      Sum of squares methods for sensor network localization\n                      , Comput. Optim. Appl., to appear."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"P. Parrilo and B. Sturmfels,\n                      Minimizing polynomial functions\n                      , in Proceedings of the DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science 2001, S. Basu and L. Gonzalez-Vega, eds., American Mathematical Society, Providence, RI, 2003, pp. 83\u2013100.","DOI":"10.1090\/dimacs\/060\/08"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0387-5"},{"key":"R24","unstructured":"P. Parrilo,\n                      Exploiting structure in sum of squares programs\n                      , in Proceedings for the 42nd IEEE Conference on Decision and Control, Maui, Hawaii, 2003."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-78-04519-2"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/050647098"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805766"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/050623802"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds.\n                      Handbook of semidefinite programming\n                      , Kluwer Publishers, Boston, 2000.","DOI":"10.1007\/978-1-4615-4381-7"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060668791","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:26:09Z","timestamp":1787333169000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060668791"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12,31]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/060668791"],"URL":"https:\/\/doi.org\/10.1137\/060668791","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,12,31]]}}}