{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T20:17:10Z","timestamp":1790713030597,"version":"4.1.0"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CAREER-ECCS-1651433"],"award-info":[{"award-number":["CAREER-ECCS-1651433"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1447470"],"award-info":[{"award-number":["IIS-1447470"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>In this paper, we develop a unified framework capable of certifying both exponential and subexponential convergence rates for a wide range of iterative first-order optimization algorithms. To this end, we construct a family of parameter-dependent nonquadratic Lyapunov functions that can generate convergence rates in addition to proving asymptotic convergence. Using integral quadratic constraints (IQCs) from robust control theory, we propose a linear matrix inequality (LMI) to guide the search for the parameters of the Lyapunov function in order to establish a rate bound. Based on this result, we develop a semidefinite programming (SDP) framework whose solution yields the best convergence rate that can be certified by the class of Lyapunov functions under consideration. We illustrate the utility of our results by analyzing the gradient method, proximal algorithms, and their accelerated variants for (strongly) convex problems. We also develop the continuous-time counterpart, whereby we analyze the gradient flow and the continuous-time limit of Nesterov's accelerated method.<\/jats:p>","DOI":"10.1137\/17m1136845","type":"journal-article","created":{"date-parts":[[2018,9,20]],"date-time":"2018-09-20T10:06:42Z","timestamp":1537438002000},"page":"2654-2689","source":"Crossref","is-referenced-by-count":71,"title":["Analysis of Optimization Algorithms via Integral Quadratic Constraints: Nonstrongly Convex Problems"],"prefix":"10.1137","volume":"28","author":[{"given":"Mahyar","family":"Fazlyab","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alejandro","family":"Ribeiro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manfred","family":"Morari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Victor M.","family":"Preciado","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,9,20]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012998335802"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jde.2016.08.020"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"atypb4","unstructured":"D. P. Bertsekas,\n                      Convex Optimization Algorithms\n                      , Athena Scientific, 2015."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-09-04785-0"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2017.2778689"},{"key":"atypb7","first-page":"185","author":"Combettes P. L.","year":"2011","journal-title":"Springer"},{"key":"atypb8","first-page":"1376","author":"Cyrus S.","year":"2018","journal-title":"IEEE"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0677-5"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0653-0"},{"key":"atypb11","first-page":"354","author":"Fazlyab M.","year":"2017","journal-title":"IEEE"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2010.08.011"},{"key":"atypb13","unstructured":"M. Hardt, T. Ma, and B. Recht,\n                      Gradient Descent Learns Linear Dynamical Systems\n                      , preprint,https:\/\/arxiv.org\/abs\/1609.05191, 2016."},{"key":"atypb14","first-page":"1594","author":"Hazan E.","year":"2015","journal-title":"Inc."},{"key":"atypb15","first-page":"3114","author":"Hu B.","year":"2017","journal-title":"IEEE"},{"key":"atypb16","unstructured":"B. Hu and L. Lessard,\n                      Dissipativity theory for Nesterov'\u0092s accelerated method\n                      , in Proceedings of the Thirty-Fourth International Conference on Machine Learning, Proc. Mach. Learn. Res. 70, International Machine Learning Society (IMLS), 2017, pp. 1549-1557."},{"key":"atypb17","first-page":"795","author":"Karimi H.","year":"2016","journal-title":"Springer"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0949-3"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/15M1009597"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1109\/9.587335"},{"key":"atypb21","first-page":"1","author":"Necoara I.","year":"2018","journal-title":"Math. Program."},{"key":"atypb22","first-page":"372","volume":"27","author":"Nesterov Y.","year":"1983","journal-title":"Soviet Math. Dokl."},{"key":"atypb23","unstructured":"Y. Nesterov,\n                      Introductory Lectures on Convex Optimization: A Basic Course\n                      , Appl. Optim. 87, Kluwer Academic Publishers, 2013."},{"key":"atypb24","unstructured":"R. Nishihara, L. Lessard, B. Recht, A. Packard, and M. I. Jordan,\n                      A General Analysis of the Convergence of ADMM\n                      , preprint,https:\/\/arxiv.org\/abs\/1502.02009, 2015."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(64)90137-5"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2011.2176389"},{"key":"atypb27","first-page":"1","volume":"17","author":"Su W.","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-018-1298-1"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1009-3"},{"key":"atypb30","first-page":"557","author":"Wang J.","year":"2010","journal-title":"IEEE"},{"key":"atypb31","first-page":"3800","author":"Wang J.","year":"2011","journal-title":"IEEE"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1614734113"},{"key":"atypb33","unstructured":"A. C. Wilson, B. Recht, and M. I. Jordan,\n                      A Lyapunov Analysis of Momentum Methods in Optimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1611.02635, 2016."},{"key":"atypb34","unstructured":"V. Yakubovich,\n                      Frequency conditions for the absolute stability of control systems with several nonlinear or linear nonstationary blocks\n                      , Avtomat. i Telemekh., 6 (1967), pp. 5-30 (in Russian)."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1136845","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:19:41Z","timestamp":1787339981000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1136845"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1136845"],"URL":"https:\/\/doi.org\/10.1137\/17m1136845","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}