In this note, we show a sublinear nonergodic convergence rate for the algorithm developed in [Bai, et al Generalized symmetric ADMM for separable convex optimization. Comput. Optim. Appl. 70, 129-170 (2018)], as well as its linear convergence under assumptions that the sub-differential of each component objective function is piecewise linear and all the constraint sets are polyhedra. These remaining convergence results are established for the stepsize parameters of dual variables belonging to a special isosceles triangle region, which aims to strengthen our understanding for convergence of the generalized symmetric ADMM.
The algorithm GS-ADMM was initially proposed to generalize the meaningful S-ADMM @cite_4 for solving the grouped multi-block separable convex optimization problem ), whose convergence and iteration complexity could be still ensured for a larger domain of stepsizes of dual variables than that introduced in @cite_4 . In practise, convergence of GS-ADMM was analyzed by estimating the lower bound of @math directly and by treating the domain of stepsize parameters as a whole, while convergence of S-ADMM was showed separately by splitting the domain of @math into several subdomains, where @math and @math are called the predictive variable and the correcting variable, respectively. Note that by taking @math , GS-ADMM with @math will become S-ADMM but continue to converge in the relatively larger convergence domain @math . In addition, the original S-ADMM only works for the two-block case and may not be convenient for solving large-scale problems, while GS-ADMM could handle large-scale multiple block problems since the block variables within each group were updated in a Jacobian scheme.
@cite_4
2523748411
The alternating direction method of multipliers (ADMM), also well known as a special split Bregman algorithm in imaging, is being popularly used in many areas including the image processing field. One useful modification is the symmetric version of the original ADMM, which updates the Lagrange multiplier twice at each iteration and thus the variables are treated in a symmetric manner. The symmetric version of ADMM, however, is not necessarily convergent. It was recently found that the convergence of symmetric ADMM can be sufficiently ensured if both the step sizes for updating the Lagrange multiplier are shrunk conservatively. Despite the theoretical significance in ensuring convergence, however, smaller step sizes should be strongly avoided in practice. On the contrary, we actually have the desire of seeking larger step sizes whenever possible in order to accelerate the numerical performance. Another technique leading to numerical acceleration of ADMM is enlarging its step size by a constant originally p...