{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:34:09Z","timestamp":1787340849380,"version":"build-2736575974"},"reference-count":80,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007455","name":"Skolkovo Institute of Science and Technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007455","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>We consider the sequence acceleration problem for the alternating direction method of multipliers (ADMM) applied to a class of equality-constrained problems with strongly convex quadratic objectives, which frequently arise as the Newton subproblem of interior-point methods. Within this context, the ADMM update equations are linear, the iterates are confined within a Krylov subspace, and the general minimum residual (GMRES) algorithm is optimal in its ability to accelerate convergence. The basic ADMM method solves a $\\kappa$-conditioned problem in $O(\\sqrt{\\kappa})$ iterations. We give theoretical justification and numerical evidence that the GMRES-accelerated variant consistently solves the same problem in $O(\\kappa^{1\/4})$ iterations for an order-of-magnitude reduction in iterations, despite a worst-case bound of $O(\\sqrt{\\kappa})$ iterations. The method is shown to be competitive against standard preconditioned Krylov subspace methods for saddle-point problems. The method is embedded within SeDuMi, a popular open-source solver for conic optimization written in MATLAB, and used to solve many large-scale semidefinite programs with error that decreases like $O(1\/k^{2})$, instead of $O(1\/k)$, where $k$ is the iteration index.<\/jats:p>","DOI":"10.1137\/16m1059941","type":"journal-article","created":{"date-parts":[[2018,10,25]],"date-time":"2018-10-25T13:05:04Z","timestamp":1540472704000},"page":"3025-3056","source":"Crossref","is-referenced-by-count":10,"title":["GMRES-Accelerated ADMM for Quadratic Objectives"],"prefix":"10.1137","volume":"28","author":[{"given":"Richard Y.","family":"Zhang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jacob K.","family":"White","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,10,25]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614432"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2012.684353"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1947"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/090756855"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/110840819"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497328008"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1023\/B:BITN.0000014548.26616.65"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479802417106"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492904000212"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-006-0679-9"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1023\/B:COAP.0000026882.34332.1b"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"B. Borchers,\n                      SDPLIB 1.2, a library of semidefinite programming test problems\n                      , Optim. Methods Softw., 11 (1999), pp. 683-690.","DOI":"10.1080\/10556789908805769"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1561\/2200000016"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1988-0917816-8"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/0804017"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-010-0251-1"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1080\/10556780802102693"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0827"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/0903004"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-015-0048-x"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1109\/18.959265"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144596305582"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(87)90253-9"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/09076934X"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/0721026"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/BF02510258"},{"key":"atypb31","unstructured":"M. Fortin and R. Glowinski,\n                      Augmented Lagrangian Methods\n                      , North-Holland, Amsterdam, 1983."},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366218"},{"key":"atypb33","unstructured":"D. Gabay,\n                      Applications of the Method of Multipliers to Variational Inequalities\n                      , North-Holland, Amsterdam, 1983."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(76)90003-1"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2014.2354892"},{"key":"atypb36","first-page":"5033","author":"Giselsson P.","year":"2014","journal-title":"NJ"},{"key":"atypb37","first-page":"41","volume":"9","author":"Glowinski R.","year":"1975","journal-title":"ESAIM Math. Model. Numer. Anal."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/120896219"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827500375096"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-010-9361-3"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"A. Greenbaum,\n                      Iterative Methods for Solving Linear Systems\n                      , Front. Appl. Math. 17, SIAM, Philadelphia, 1997.","DOI":"10.1137\/1.9781611970937"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1137\/110836936"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386294"},{"key":"atypb44","first-page":"497","author":"Kadkhodaie M.","year":"2015","journal-title":"New York"},{"key":"atypb45","first-page":"1742","author":"Kalbat A.","year":"2015","journal-title":"NJ"},{"key":"atypb46","first-page":"302","author":"Karmarkar N.","year":"1984","journal-title":"New York"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899351805"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827597327334"},{"key":"atypb49","first-page":"5932","author":"Madani R.","year":"2015","journal-title":"NJ"},{"key":"atypb50","first-page":"189","author":"Mitchell J. E.","year":"1998","journal-title":"Boston"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1137\/0613050"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0351-9"},{"key":"atypb53","unstructured":"A. Nemirovskii, D. B. Yudin, and E. R. Dawson,\n                      Problem Complexity and Method Efficiency in Optimization\n                      , Wiley, New York, 1983."},{"key":"atypb54","first-page":"372","volume":"27","author":"Nesterov Y.","year":"1983","journal-title":"Sov. Math. Dokl."},{"key":"atypb55","doi-asserted-by":"crossref","unstructured":"Y. Nesterov,\n                      Introductory Lectures on Convex Optimization\n                      , Appl. Optim, 87, Kluwer, Boston, 2004.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0552-5"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0001-8"},{"key":"atypb58","first-page":"343","author":"Nishihara R.","year":"2015","journal-title":"PMLR"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-016-0892-3"},{"key":"atypb60","doi-asserted-by":"publisher","DOI":"10.1137\/14095697X"},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.3182\/20140824-6-ZA-1003.01647"},{"key":"atypb62","unstructured":"G. Pataki and S. Schmieta,\n                      The DIMACS Library of Semidefinite-Quadratic-Linear Programs\n                      , Technical report, Computational Optimization Research Center, Columbia University, New York, 2002."},{"key":"atypb63","first-page":"4234","author":"Patrinos P.","year":"2014","journal-title":"NJ"},{"key":"atypb64","unstructured":"T. J. Rivlin,\n                      The Chebyshev Polynomials: From Approximation Theory to Algebra and Number Theory\n                      , Wiley, New York, 1974."},{"key":"atypb65","doi-asserted-by":"publisher","DOI":"10.1145\/1255443.1255449"},{"key":"atypb66","doi-asserted-by":"publisher","DOI":"10.1137\/0613054"},{"key":"atypb67","doi-asserted-by":"crossref","unstructured":"Y. Saad,\n                      Iterative Methods for Sparse Linear Systems\n                      , 2nd ed., SIAM, Philadelphia, 2003.","DOI":"10.1137\/1.9780898718003"},{"key":"atypb68","doi-asserted-by":"publisher","DOI":"10.1137\/0907058"},{"key":"atypb69","doi-asserted-by":"publisher","DOI":"10.1016\/j.apnum.2003.11.012"},{"key":"atypb70","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479803434926"},{"key":"atypb71","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805766"},{"key":"atypb72","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623402419819"},{"key":"atypb73","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400376378"},{"key":"atypb74","doi-asserted-by":"crossref","unstructured":"L. N. Trefethen and M. Embree,\n                      Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators\n                      , Princeton University Press, Princeton, NJ, 2005.","DOI":"10.1515\/9780691213101"},{"key":"atypb75","doi-asserted-by":"publisher","DOI":"10.1561\/2400000006"},{"key":"atypb76","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585558"},{"key":"atypb77","doi-asserted-by":"publisher","DOI":"10.1137\/1038003"},{"key":"atypb78","doi-asserted-by":"publisher","DOI":"10.1137\/10078356X"},{"key":"atypb79","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-010-0017-1"},{"key":"atypb80","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492900002300"},{"key":"atypb81","first-page":"5766","author":"Zhang R. Y.","year":"2018","journal-title":"PMLR"},{"key":"atypb82","first-page":"3335","author":"Zheng Y.","year":"2017","journal-title":"NJ"},{"key":"atypb83","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-01-01324-2"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1059941","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:52:14Z","timestamp":1787338334000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1059941"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":80,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1059941"],"URL":"https:\/\/doi.org\/10.1137\/16m1059941","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}