Convergence Rate Analysis for the Alternating Direction Method of Multipliers with a Substitution Procedure for Separable Convex Programming

Bingsheng He (), Min Tao () and Xiaoming Yuan ()
Additional contact information
Bingsheng He: Department of Mathematics, South University of Science and Technology of China, Shenzhen 518055, China; Department of Mathematics, Nanjing University, Nanjing 210093, China
Min Tao: Department of Mathematics, Nanjing University, Nanjing, 210093, China
Xiaoming Yuan: Department of Mathematics, Hong Kong Baptist University, Hong Kong, China

Mathematics of Operations Research, 2017, vol. 42, issue 3, 662-691

Abstract: Recently, in He et al. [He BS, Tao M, Yuan XM (2012) Alternating direction method with Gaussian back substitution for separable convex programming. SIAM J. Optim. 22(2):313–340], we have showed the first possibility of combining the Douglas-Rachford alternating direction method of multipliers (ADMM) with a Gaussian back substitution procedure for solving a convex minimization model with a general separable structure. This paper is a further study on this theme. We first derive a general algorithmic framework to combine ADMM with either a forward or backward substitution procedure. Then, we show that convergence of this framework can be easily proved from the contraction perspective, and its local linear convergence rate is provable if certain error bound condition is assumed. Without such an error bound assumption, we can estimate its worst-case convergence rate measured by the iteration complexity.

Keywords: convex programming; alternating direction method of multipliers; convergence rate; iteration complexity; contraction methods (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0822 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:42:y:2017:i:3:p:662-691

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().