{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,9]],"date-time":"2026-10-09T00:26:49Z","timestamp":1791505609038,"version":"4.3.4"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["U01 EB018753"],"award-info":[{"award-number":["U01 EB018753"]}],"id":[{"id":"10.13039\/100000002","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>This paper generalizes the optimized gradient method (OGM) [Y. Drori and M. Teboulle, Math. Program., 145 (2014), pp. 451--482], [D. Kim and J. A. Fessler, Math. Program., 159 (2016), pp. 81--107], [D. Kim and J. A. Fessler, J. Optim. Theory Appl., 172 (2017), pp. 187--205] that achieves the optimal worst-case cost function bound of first-order methods for smooth convex minimization [Y. Drori, J. Complexity, 39 (2017), pp. 1--16]. Specifically, this paper studies a generalized formulation of OGM and analyzes its worst-case rates in terms of both the function value and the norm of the function gradient. This paper also develops a new algorithm called OGM-OG that is in the generalized family of OGM and that has the best known analytical worst-case bound with rate $O(1\/N^{1.5})$ on the decrease of the gradient norm among fixed-step first-order methods. This paper also proves that Nesterov's fast gradient method [Y. Nesterov, Dokl. Akad. Nauk. USSR, 269 (1983), pp. 543--547], [Y. Nesterov, Math. Program., 103 (2005), pp. 127--152] has an $O(1\/N^{1.5})$ worst-case gradient norm rate but with constant larger than OGM-OG. The proof is based on the worst-case analysis called the Performance Estimation Problem in [Y. Drori and M. Teboulle, Math. Program., 145 (2014), pp. 451--482].<\/jats:p>","DOI":"10.1137\/17m112124x","type":"journal-article","created":{"date-parts":[[2018,6,28]],"date-time":"2018-06-28T12:25:53Z","timestamp":1530188753000},"page":"1920-1950","source":"Crossref","is-referenced-by-count":26,"title":["Generalizing the Optimized Gradient Method for Smooth Convex Minimization"],"prefix":"10.1137","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1816-5917","authenticated-orcid":true,"given":"Donghwan","family":"Kim","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey A.","family":"Fessler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,6,28]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-0992-8"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-015-0746-4"},{"key":"atypb4","unstructured":"CVX Research Inc.\n                      CVX: MATLAB Software for Disciplined Convex Programming, Version\n                      2.0,http:\/\/cvxr.com\/cvx, 2012."},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"E. de Klerk, F. Glineur, and A. B. Taylor,\n                      On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions\n                      , Optim. Lett. (2017),https:\/\/doi.org\/10.1007\/s11590-016-1087-4.","DOI":"10.1007\/s11590-016-1087-4"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/110826102"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2016.11.001"},{"key":"atypb8","unstructured":"Y. Drori and A. B. Taylor,\n                      Efficient First-Order Methods for Convex Minimization: A Constructive Approach\n                      , preprint,http:\/\/arxiv.org\/abs\/1803.05676, 2018."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0653-0"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-0985-7"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0871-8"},{"key":"atypb12","first-page":"95","author":"Grant M.","year":"2008","journal-title":"Springer-Verlag Limited"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/0802032"},{"key":"atypb14","first-page":"3675","author":"Kim D.","year":"2015","journal-title":"Proc. IEEE Intl. Conf. on Image Processing"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0949-3"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-016-1018-7"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/16M108940X"},{"key":"atypb18","unstructured":"D. Kim and J. A. Fessler,\n                      Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions\n                      , preprint,http:\/\/arxiv.org\/abs\/1803.06600, 2018."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/15M1009597"},{"key":"atypb20","unstructured":"J. Lo\u0308fberg,\n                      YALMIP: A toolbox for modeling and optimization in MATLAB\n                      , in Proceedings of the CACSD Conference, Taipei, Taiwan, 2004."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/110833786"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2016.1161763"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(92)90013-2"},{"key":"atypb24","first-page":"543","volume":"269","author":"Nesterov Y.","year":"1983","journal-title":"Dokl. Akad. Nauk. USSR"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"Y. Nesterov,\n                      Introductory Lectures on Convex Optimization: A Basic Course\n                      , Kluwer, 2004,https:\/\/doi.org\/10.1007\/978-1-4419-8853-9.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0552-5"},{"key":"atypb27","first-page":"10","volume":"88","author":"Nesterov Y.","year":"2012","journal-title":"Optima"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"J. Sturm,\n                      Using SeDuMi 1.02, A MATLAB toolbox for optimization over symmetric cones\n                      , Optim. Methods Softw., 11 (1999), pp. 625-653,https:\/\/doi.org\/10.1080\/10556789908805766.","DOI":"10.1080\/10556789908805766"},{"key":"atypb29","first-page":"1","volume":"17","author":"Su W.","year":"2016","journal-title":"J. Mach. Learning Res."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/16M108104X"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1009-3"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M112124X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:04:12Z","timestamp":1787339052000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M112124X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M112124X"],"URL":"https:\/\/doi.org\/10.1137\/17m112124x","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}