A class of ADMM-based algorithms for three-block separable convex programming

Bingsheng He () and Xiaoming Yuan ()
Additional contact information
Bingsheng He: Southern University of Science and Technology
Xiaoming Yuan: The University of Hong Kong

Computational Optimization and Applications, 2018, vol. 70, issue 3, No 6, 826 pages

Abstract: Abstract The alternating direction method of multipliers (ADMM) recently has found many applications in various domains whose models can be represented or reformulated as a separable convex minimization model with linear constraints and an objective function in sum of two functions without coupled variables. For more complicated applications that can only be represented by such a multi-block separable convex minimization model whose objective function is the sum of more than two functions without coupled variables, it was recently shown that the direct extension of ADMM is not necessarily convergent. On the other hand, despite the lack of convergence, the direct extension of ADMM is empirically efficient for many applications. Thus we are interested in such an algorithm that can be implemented as easily as the direct extension of ADMM, while with comparable or even better numerical performance and guaranteed convergence. In this paper, we suggest correcting the output of the direct extension of ADMM slightly by a simple correction step. The correction step is simple in the sense that it is completely free from step-size computing and its step size is bounded away from zero for any iterate. A prototype algorithm in this prediction-correction framework is proposed; and a unified and easily checkable condition to ensure the convergence of this prototype algorithm is given. Theoretically, we show the contraction property, prove the global convergence and establish the worst-case convergence rate measured by the iteration complexity for this prototype algorithm. The analysis is conducted in the variational inequality context. Then, based on this prototype algorithm, we propose a class of specific ADMM-based algorithms that can be used for three-block separable convex minimization models. Their numerical efficiency is verified by an image decomposition problem.

Keywords: Convex programming; Alternating direction method of multipliers; Splitting methods; Contraction; Convergence rate; 90C25; 90C30; 90C33 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-018-9994-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:coopap:v:70:y:2018:i:3:d:10.1007_s10589-018-9994-1

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-018-9994-1

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().