GMRES-Accelerated ADMM for Quadratic Objectives
© 2018 Society for Industrial and Applied Mathematics. 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 subprob...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Society for Industrial & Applied Mathematics (SIAM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/135162 |
| _version_ | 1826199506631262208 |
|---|---|
| author | Zhang, Richard Y White, Jacob K |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Zhang, Richard Y White, Jacob K |
| author_sort | Zhang, Richard Y |
| collection | MIT |
| description | © 2018 Society for Industrial and Applied Mathematics. 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 Κ -conditioned problem in O(√Κ) iterations. We give theoretical justification and numerical evidence that the GMRES-accelerated variant consistently solves the same problem in O(Κ 1 / 4 ) iterations for an order-of-magnitude reduction in iterations, despite a worst-case bound of O(√Κ) 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. |
| first_indexed | 2024-09-23T11:21:20Z |
| format | Article |
| id | mit-1721.1/135162 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:21:20Z |
| publishDate | 2021 |
| publisher | Society for Industrial & Applied Mathematics (SIAM) |
| record_format | dspace |
| spelling | mit-1721.1/1351622023-12-12T19:47:31Z GMRES-Accelerated ADMM for Quadratic Objectives Zhang, Richard Y White, Jacob K Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science © 2018 Society for Industrial and Applied Mathematics. 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 Κ -conditioned problem in O(√Κ) iterations. We give theoretical justification and numerical evidence that the GMRES-accelerated variant consistently solves the same problem in O(Κ 1 / 4 ) iterations for an order-of-magnitude reduction in iterations, despite a worst-case bound of O(√Κ) 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. 2021-10-27T20:11:02Z 2021-10-27T20:11:02Z 2018 2019-07-09T15:08:22Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/135162 en 10.1137/16M1059941 SIAM Journal on Optimization Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial & Applied Mathematics (SIAM) SIAM |
| spellingShingle | Zhang, Richard Y White, Jacob K GMRES-Accelerated ADMM for Quadratic Objectives |
| title | GMRES-Accelerated ADMM for Quadratic Objectives |
| title_full | GMRES-Accelerated ADMM for Quadratic Objectives |
| title_fullStr | GMRES-Accelerated ADMM for Quadratic Objectives |
| title_full_unstemmed | GMRES-Accelerated ADMM for Quadratic Objectives |
| title_short | GMRES-Accelerated ADMM for Quadratic Objectives |
| title_sort | gmres accelerated admm for quadratic objectives |
| url | https://hdl.handle.net/1721.1/135162 |
| work_keys_str_mv | AT zhangrichardy gmresacceleratedadmmforquadraticobjectives AT whitejacobk gmresacceleratedadmmforquadraticobjectives |