{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T16:07:22Z","timestamp":1784563642642,"version":"3.55.0"},"reference-count":54,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-22-1-0225"],"award-info":[{"award-number":["FA9550-22-1-0225"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-23-1-0070"],"award-info":[{"award-number":["FA9550-23-1-0070"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2026,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We present a hierarchy of tractable relaxations to obtain lower bounds on the minimum value of a polynomial over a constraint set defined by polynomial equations.\u00a0In contrast to previous convex relaxation techniques for this problem, our method is based on computing the smallest generalized eigenvalue of a pair of matrices derived from the problem data, which can be accomplished for large problem instances using off-the-shelf software. We characterize the algebraic structure in a problem that facilitates the application of our framework, and we observe that our method is applicable for all polynomial optimization problems with bounded constraint sets.\u00a0Our construction also yields a nested sequence of structured convex outer approximations of a bounded algebraic variety with the property that linear optimization over each approximation reduces to an eigenvalue computation.\u00a0Finally, we present numerical experiments on representative problems in which we demonstrate the scalability of our approach compared to convex relaxation methods derived from sums-of-squares certificates of nonnegativity.<\/jats:p>","DOI":"10.1137\/25m1781942","type":"journal-article","created":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T15:41:20Z","timestamp":1784562080000},"page":"1563-1588","source":"Crossref","is-referenced-by-count":0,"title":["Spectral Methods for Polynomial Optimization"],"prefix":"10.1137","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0477-7744","authenticated-orcid":true,"given":"Elvira","family":"Moreno","sequence":"first","affiliation":[{"name":"Department of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA 91125 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Venkat","family":"Chandrasekaran","sequence":"additional","affiliation":[{"name":"Departments of Computing and Mathematical Sciences and of Electrical Engineering, California Institute of Technology, Pasadena, CA 91125 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,7,21]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"A. A. Ahmadi, G. Hall, A. Papachristodoulou, J. Saunderson, and Y. Zheng, Improving efficiency and scalability of sum of squares optimization:\u00a0Recent advances and limitations, in Proceedings of the 56th Annual Conference on Decision and Control (CDC), IEEE, 2017, pp. 453\u2013462, https:\/\/doi.org\/10.1109\/CDC.2017.8263706.","DOI":"10.1109\/CDC.2017.8263706"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-015-0894-3"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/18M118935X"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719604"},{"key":"ref5","unstructured":"A. S. Bandeira, C. Kennedy, and A. Singer, Approximating the Little Grothendieck Problem over the Orthogonal Group, https:\/\/arxiv.org\/abs\/1308.5207, 2013."},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"J. Berthomieu, C. Eder, and M. Safey El Din,\n                      msolve:\u00a0A library for solving polynomial systems\n                      , in Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC \u201921), Association for Computing Machinery, New York, 2021, pp. 51\u201358, https:\/\/doi.org\/10.1145\/3452143.3465545.","DOI":"10.1145\/3452143.3465545"},{"key":"ref7","series-title":"MOS-SIAM Ser. Optim.","volume-title":"Semidefinite Optimization and Convex Algebraic Geometry","author":"Blekherman G.","year":"2013"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"B. Buchberger and F. Winkler, eds. Gr\u00f6bner Bases and Applications, Cambridge University Press, 1998.","DOI":"10.1017\/CBO9780511565847"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-023-02168-6"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/140988978"},{"key":"ref11","volume-title":"Ideals, Varieties, and Algorithms:\u00a0An Introduction to Computational Algebraic Geometry and Commutative Algebra","author":"Cox D. A.","year":"2010","edition":"3"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1137\/22M1484511"},{"key":"ref13","unstructured":"W. Decker, G.M. Greuel, G. Pfister, and H. Sch\u00f6nemann, Singular 4-4-0 \u2014 A Computer Algebra System for Polynomial Computations, 2024, http:\/\/www.singular.uni-kl.de."},{"key":"ref14","first-page":"1","volume":"17","author":"Diamond S.","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1137\/16M1086303"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479895290954"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01537-7"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2003.12.011"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1137\/090746525"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198510581.001.0001"},{"key":"ref21","unstructured":"D. R. Grayson and M. E. Stillman, Macaulay2, A Software System for Research in Algebraic Geometry, http:\/\/www2.macaulay2.com."},{"key":"ref22","unstructured":"G. Hall, Engineering and Business Applications of Sum of Squares Polynomials, https:\/\/arxiv.org\/abs\/1906.07961, 2019."},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-012-0601-0"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497328987"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1142\/q0252"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/3607"},{"key":"ref28","series-title":"Information and Interdisciplinary Subjects Series 10","volume-title":"Moments, Positive Polynomials and Their Applications","author":"Lasserre J.","year":"2010"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11 (2001), pp. 796\u2013817, https:\/\/doi.org\/10.1137\/S1052623400366802.","DOI":"10.1137\/S1052623400366802"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1137\/100806990"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107447226"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719628"},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"B. Lovitz and N. Johnston, A Hierarchy of Eigencomputations for Polynomial Optimization on the Sphere, https:\/\/arxiv.org\/abs\/2310.17827, 2024.","DOI":"10.1007\/s10107-025-02251-y"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-023-00243-7"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/146"},{"key":"ref36","unstructured":"MOSEK Python API Manual Version 10.2, 2025, https:\/\/docs.mosek.com\/10.2\/pythonapi\/index.html."},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-020-00193-4"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-021-09497-w"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592948"},{"key":"ref40","doi-asserted-by":"crossref","unstructured":"J. Nie and L. Wang, Regularization methods for SDP relaxations in large-scale polynomial optimization, SIAM J. Optim., 22 (2012), pp. 408\u2013428, https:\/\/doi.org\/10.1137\/110825844.","DOI":"10.1137\/110825844"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1137\/21M1455899"},{"key":"ref42","unstructured":"P. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization, Ph.D. thesis, California Institute of Technology, 2000, https:\/\/doi.org\/10.7907\/2K6Y-CH43."},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0387-5"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972290.ch3"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-020-01029-x"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0558"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1137\/090767777"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1137\/050623802"},{"key":"ref49","doi-asserted-by":"crossref","unstructured":"J. Wang, H. Li, and B. Xia, A new sparse SOS decomposition algorithm based on term sparsity, in Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2019, pp. 347\u2013354.","DOI":"10.1145\/3326229.3326254"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1137\/20M1323564"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1145\/3569709"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-017-0121-6"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0584-1"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1109\/LCSYS.2017.2706941"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T15:41:30Z","timestamp":1784562090000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/25M1781942"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,21]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9,30]]}},"alternative-id":["10.1137\/25M1781942"],"URL":"https:\/\/doi.org\/10.1137\/25m1781942","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,21]]}}}