{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T23:49:15Z","timestamp":1790812155359,"version":"4.1.0"},"reference-count":39,"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":[[2018,1]]},"abstract":"<jats:p>We propose a multigrid approach for the global optimization of polynomial optimization problems with sparse support. The problems we consider arise from the discretization of infinite dimensional optimization problems, such as PDE optimization problems, boundary value problems, and some global optimization applications. In many of these applications, the level of discretization can be used to obtain a hierarchy of optimization models that capture the underlying infinite dimensional problem at different degrees of fidelity. This approach, inspired by multigrid methods, has been successfully used for decades to solve large systems of linear equations. However, multigrid methods are difficult to apply to semidefinite programming (SDP) relaxations of polynomial optimization problems. The main difficulty is that the information between grids is lost when the original problem is approximated via an SDP relaxation. Despite the loss of information, we develop a multigrid approach and propose prolongation operators to relate the primal and dual variables of the SDP relaxation between lower and higher levels in the hierarchy of discretizations. We develop sufficient conditions for the operators to be useful in practice. Our conditions are easy to verify, and we discuss how they can be used to reduce the complexity of infeasible interior point methods. Our preliminary results highlight two promising advantages of following a multigrid approach compared to a pure interior point method: the percentage of problems that can be solved to a high accuracy is much greater, and the time necessary to find a solution can be reduced significantly, especially for large scale problems.<\/jats:p>","DOI":"10.1137\/16m1109060","type":"journal-article","created":{"date-parts":[[2018,1,5]],"date-time":"2018-01-05T16:39:07Z","timestamp":1515170347000},"page":"1-29","source":"Crossref","is-referenced-by-count":7,"title":["A Multigrid Approach to SDP Relaxations of Sparse Polynomial Optimization Problems"],"prefix":"10.1137","volume":"28","author":[{"given":"Juan S.","family":"Campos","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Panos","family":"Parpas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,1,5]]},"reference":[{"key":"atypb1","first-page":"1","author":"Blair J. R. S.","year":"1993","journal-title":"Springer-Verlag"},{"key":"atypb2","first-page":"1","author":"Bomze I. M.","year":"1999","journal-title":"Springer"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012901393432"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"A. Borzi\u0300 and V. Schulz,\n                      Computational Optimization of Systems Governed by Partial Differential Equations\n                      , Comput. Sci. Eng. 8, SIAM, 2011,https:\/\/doi.org\/10.1137\/1.9781611972054.","DOI":"10.1137\/1.9781611972054"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/060671590"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"W. L. Briggs, V. E. Henson, and S. F. McCormick,\n                      A Multigrid Tutorial\n                      , 2nd ed., SIAM, Philadelphia, 2000,https:\/\/doi.org\/10.1137\/1.9780898719505.","DOI":"10.1137\/1.9780898719505"},{"key":"atypb7","unstructured":"D. Cox, J. Little, and D. O'shea,\n                      Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra\n                      , Springer-Verlag, 1992."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-00-01184-4"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"M. C. Golumbic,\n                      Algorithmic Graph Theory and Perfect Graphs\n                      , 2nd ed., Ann. Discrete Math. 57, Elsevier, 2004.","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/050623012"},{"key":"atypb11","first-page":"293","author":"Henrion D.","year":"2005","journal-title":"Springer"},{"key":"atypb12","unstructured":"M. Hinze, R. Pinnau, M. Ulbrich, and S. Ulbrich,\n                      Optimization with PDE Constraints\n                      , Math. Model. Theory Appl. 23, Springer Science+Business Media, 2008."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/130944254"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"R. A. Horn and C. R. Johnson,\n                      Matrix Analysis\n                      , Cambridge University Press, 2012.","DOI":"10.1017\/CBO9781139020411"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/15M104013X"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/05064504X"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"J. B. Lasserre,\n                      An Introduction to Polynomial and Semi-algebraic Optimization\n                      , Cambridge Texts Appl. Math. 52, Cambridge University Press, 2015.","DOI":"10.1017\/CBO9781107447226"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/070685051"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"F. Lin, Z. Di, and S. Leyffer,\n                      A multiscale approach to a class of semidefinite programs\n                      , to in Proceedings of the 2016 American Control Conference, IEEE, pp. 7153-7158.","DOI":"10.1109\/ACC.2016.7526801"},{"key":"atypb21","first-page":"213","volume":"4","author":"Mevissen M.","year":"2008","journal-title":"P. J. Optim."},{"key":"atypb22","first-page":"10887","author":"Mevissen M.","year":"2011","journal-title":"Elsevier"},{"key":"atypb23","first-page":"252","author":"Mevissen M.","year":"2009","journal-title":"ACM"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1145\/355934.355936"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/0721052"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1080\/10556780008805795"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/060668791"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016259507911"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0387-5"},{"key":"atypb30","first-page":"83","author":"Parrilo P. A.","year":"2003","journal-title":"American Mathematical Society"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623495294955"},{"key":"atypb32","first-page":"5605","author":"Raghunathan A. U.","year":"2016","journal-title":"IEEE"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"Y. Saad,\n                      Iterative Methods for Sparse Linear Systems\n                      , SIAM, Philadelphia, 2003,https:\/\/doi.org\/10.1137\/1.9780898718003.","DOI":"10.1137\/1.9780898718003"},{"key":"atypb34","first-page":"715","author":"Toh K.-C.","year":"2012","journal-title":"Springer"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"L. Vandenberghe and M. S. Andersen,\n                      Chordal Graphs and Semidefinite Optimization\n                      , Now Publishers Incorporated, 2015.","DOI":"10.1561\/9781680830392"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/050623802"},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"H. Waki, S. Kim, M. Kojima, M. Muramatsu, and H. Sugimoto,\n                      Algorithm 883: Sparsepop-a sparse semidefinite programming relaxation of polynomial optimization problems\n                      , ACM Trans. Math. Software (TOMS), 35 (2008), 15.","DOI":"10.1145\/1377612.1377619"},{"key":"atypb38","first-page":"1","author":"Weisser T.","year":"2017","journal-title":"Math. Prog. Comput."},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/08071524X"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1109060","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:45Z","timestamp":1787336085000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1109060"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1109060"],"URL":"https:\/\/doi.org\/10.1137\/16m1109060","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}