Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/93884
Title: | On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming | Authors: | Chen, L Li, X Sun, D Toh, KC |
Issue Date: | Jan-2021 | Source: | Mathematical programming, Jan. 2021, v. 185, no. 1-2, p. 111-161 | Abstract: | In this paper, we show that for a class of linearly constrained convex composite optimization problems, an (inexact) symmetric Gauss–Seidel based majorized multi-block proximal alternating direction method of multipliers (ADMM) is equivalent to an inexact proximal augmented Lagrangian method. This equivalence not only provides new perspectives for understanding some ADMM-type algorithms but also supplies meaningful guidelines on implementing them to achieve better computational efficiency. Even for the two-block case, a by-product of this equivalence is the convergence of the whole sequence generated by the classic ADMM with a step-length that exceeds the conventional upper bound of (1+5)/2, if one part of the objective is linear. This is exactly the problem setting in which the very first convergence analysis of ADMM was conducted by Gabay and Mercier (Comput Math Appl 2(1):17–40, 1976), but, even under notably stronger assumptions, only the convergence of the primal sequence was known. A collection of illustrative examples are provided to demonstrate the breadth of applications for which our results can be used. Numerical experiments on solving a large number of linear and convex quadratic semidefinite programming problems are conducted to illustrate how the theoretical results established here can lead to improvements on the corresponding practical implementations. | Keywords: | Alternating direction method of multipliers Augmented Lagrangian method Proximal term Symmetric Gauss–Seidel decomposition |
Publisher: | Springer | Journal: | Mathematical programming | ISSN: | 0025-5610 | DOI: | 10.1007/s10107-019-01423-x | Rights: | © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2019 This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use (https://www.springernature.com/gp/open-research/policies/accepted-manuscript-terms), but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/s10107-019-01423-x |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Chen_Equivalence_Inexact_Proximal.pdf | Pre-Published version | 999.89 kB | Adobe PDF | View/Open |
Page views
49
Last Week
1
1
Last month
Citations as of Apr 28, 2024
Downloads
41
Citations as of Apr 28, 2024
SCOPUSTM
Citations
20
Citations as of May 3, 2024
WEB OF SCIENCETM
Citations
22
Citations as of May 2, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.