Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

An alternating direction method of multipliers with a worst-case $ O(1/n^2)$ convergence rate


Authors: Wenyi Tian and Xiaoming Yuan
Journal: Math. Comp. 88 (2019), 1685-1713
MSC (2010): Primary 90C25, 65K10
DOI: https://doi.org/10.1090/mcom/3388
Published electronically: December 12, 2018
MathSciNet review: 3925481
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: The alternating direction method of multipliers (ADMM) is being widely used for various convex programming models with separable structures arising in many scientific computing areas. The ADMM's worst-case $ O(1/n)$ convergence rate measured by the iteration complexity has been established in the literature when its penalty parameter is a constant, where $ n$ is the iteration counter. Research on ADMM's worst-case $ O(1/n^2)$ convergence rate, however, is still in its infancy. In this paper, we suggest applying a rule proposed recently by Chambolle and Pock to iteratively update the penalty parameter and show that the ADMM with this adaptive penalty parameter has a worst-case $ O(1/n^2)$ convergence rate in the ergodic sense. Without a strong convexity requirement on the objective function, our assumptions on the model are mild and can be satisfied by some representative applications. We test the least absolute shrinkage and selection operator (LASSO) model and numerically verify the significant acceleration effectiveness of the faster ADMM with a worst-case $ O(1/n^2)$ convergence rate. Moreover, the faster ADMM is more favorable than the ADMM with a constant penalty parameter, as the former is much less sensitive to the initial value of the penalty parameter and can sometimes produce very high-accuracy solutions.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 90C25, 65K10

Retrieve articles in all journals with MSC (2010): 90C25, 65K10


Additional Information

Wenyi Tian
Affiliation: Center for Applied Mathematics, Tianjin University, Tianjin 300072, People’s Republic of China
Email: twymath@gmail.com

Xiaoming Yuan
Affiliation: Department of Mathematics, The University of Hong Kong, Hong Kong, People’s Republic of China
Email: xmyuan@hku.hk

DOI: https://doi.org/10.1090/mcom/3388
Keywords: Convex programming, alternating direction method of multipliers, convergence rate, acceleration, first order methods
Received by editor(s): July 20, 2016
Received by editor(s) in revised form: September 3, 2017, May 9, 2018, and June 8, 2018
Published electronically: December 12, 2018
Additional Notes: The first author was partially supported by the National Natural Science Foundation of China (No. 11701416).
The second author was partially supported by the General Research Fund from Hong Kong Research Grants Council: 12313516.
Article copyright: © Copyright 2018 American Mathematical Society