近年来，多块交替方向乘子法被广泛地应用在信号处理、图像处理、机器学习、工程计算等各个领域中，然而它的收敛性一直是一个悬而未决的公开问题；直至2016年，陈彩华等人给出了一个三维线性方程组构成的反例说明多块交替方向乘子法是可能发散的.结合陈等人的结果，现讨论了与此相关的三个问题：1）反例之所以发散是否由于初始点选择不够好?2）反例的发散是否因为它的可行域是单点集?3）是否能够在对偶变量更新中引入某一与问题无关的步长γ∈（0，1]使得小步长的交替方向乘子法变形收敛?从理论上对前两个问题给出了否定的回答，证明当初始点随机选取时，存在可行域不是单点集的例子，使得多块交替方向乘子法求解该问题时以概率1发散；从数值上否定了第三个问题，说明即使步长γ=10-8，多块交替方向乘子法也可能发散.
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.
[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.
