Recently, multi-block alternating direction method of multipliers (ADMM) has been widely used in signal processing, image processing, machine learning, engineering calculation and so on. However its convergence had been ambiguous for a long time. In 2016, Chen Caihua, et al. gave a counter-example constructed by a threedimensional linear equations to illustrate the possible convergence of multi-block ADMM. In this paper we discuss three related issues in the light of the results Chen's:1) is the divergence of the counter-example due to the initial point selection? 2) is the divergence of the counter-example due to its singleton feasible region? 3) Whether it is possible to introduce a problem-independent step-length in the dual update γ ∈ (0, 1] such that the small step-size ADMM variant converges? In theory, the paper gives negative answers to the first two questions, and we prove that when the initial point is randomly selected, there is an example where the feasible region is not a singleton such that the multi-block ADMM is divergent with probability of 1. The third problem is negated numerically and we show that even if the step-size is γ=10-8, the multi-block ADMM can still diverge.
CHEN Caihua
. Some notes on the divergence example for multi-block alternating direction method of multipliers[J]. Operations Research Transactions, 2019
, 23(3)
: 135
-140
.
DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.010
[1] Peng Y G, Ganesh A, Wright J, et al, Robust alignment by sparse andlow-rank decomposition for linearly correlated images[J]. IEEETransactions on Pattern Analysis and Machine Intelligence, 2012,34:2233-2246.
[2] Tao M, Yuan X M. Recovering low-rank and sparse components ofmatrices from incomplete and noisy observations[J]. SIAMJournal on Optimization, 2011, 21:57-81.
[3] Chandrasekaran V, Parrilo P A, Willsky A S. Latent variablegraphical model selection via convex optimization[J]. Annalsof Statistics, 2012, 40:1935-1967.
[4] Glowinski R, Marrocco A. Approximation par éléments finis d'ordre un et résolution par pénalisation-dualitéd'une classe de problèmes non linéaires[J]. R.A.I.R.O., 1972, R2:41-76.
[5] Fortin M, Glowinski R. Decomposition-Coordination MethodsUsing an Augmented Lagrangian[M]//Fortin M and Glowinski R,editors. Augmented Lagrangian Methods:Applications to thesolution of Boundary Problems. Amsterdam:North-Holland, 1983.
[6] Han D R, Yuan X M. A note on the alternating direction method of multipliers[J].Journal of Optimization Theory and Applications, 2012,155:227-238.
[7] Lin T Y, Ma S Q, Zhang S Z, On the sublinear convergence rate ofmulti-block ADMM[J]. Journal of the Operations ResearchSociety of China, 2015, 3:251-274.
[8] Cai X J, Han D R, Yuan X M. On the convergence of the directextension of ADMM for three-block separable convex minimizationmodels is convergent when one function is strongly convex[J]. Computational Optimization and Applications, 2017, 66:39-73.
[9] Li M, Sun D F, Toh K C. A convergent 3-block semi-proximal ADMM forconvex minimization problems with one strongly convex block[J]. Asia Pacific Journal of Operational Research, 2015, 32:1550024.
[10] Chen C H, He B S, Ye Y Y et al.The direct extension of ADMM for multi-block convex minimizationproblems is not necessarily convergent[J]. MathematicalProgramming, 2016, 155:57-79.
[11] Chen C H, Sun R Y, Ye Y Y. On convergence of the multi-blockalternating direction method of multipliers[M]//Proceedingsof International Council for Industrial and Applied Mathematics(ICIAM). Beijing:Higer Education Press, 2015:3-16.
