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

He, Bingsheng1,2; Yuan, Xiaoming3

2018-07

10.1007/s10589-018-9994-1

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS   影响因子和分区

0926-6003

1573-2894

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.

Convex programming Alternating direction method of multipliers Splitting methods Contraction Convergence rate

SCI ; EI

英语

第一

Research Grants Council, University Grants Committee[HKBU 12313516]

Operations Research & Management Science ; Mathematics

Operations Research & Management Science ; Mathematics, Applied

WOS:000434145000006

SPRINGER

20182405299883

Convex optimization ; Shrinkage ; Variational techniques

Calculus:921.2 ; Numerical Methods:921.6 ; Materials Science:951

ENGINEERING

Web of Science

1.Southern Univ Sci & Technol, Dept Math, Shenzhen 518055, Peoples R China
2.Nanjing Univ, Dept Math, Nanjing 210093, Jiangsu, Peoples R China
3.Univ Hong Kong, Dept Math, Hong Kong, Hong Kong, Peoples R China

He, Bingsheng,Yuan, Xiaoming. A class of ADMM-based algorithms for three-block separable convex programming[J]. COMPUTATIONAL OPTIMIZATION AND APPLICATIONS,2018,70(3):791-826.

He, Bingsheng,&Yuan, Xiaoming.(2018).A class of ADMM-based algorithms for three-block separable convex programming.COMPUTATIONAL OPTIMIZATION AND APPLICATIONS,70(3),791-826.

He, Bingsheng,et al."A class of ADMM-based algorithms for three-block separable convex programming".COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 70.3(2018):791-826.