Generalized symmetric ADMM for separable convex optimization. Issue 1 (May 2018)

• Record Type: Journal Article
• Authors: Bai, Jianchao; Li, Jicheng; Xu, Fengmin; Zhang, Hongchao
• Is Part Of: Computational optimization and applications. Volume 70:Issue 1(2018)
• Page Start: 129
• Page End: 170
• Publication Date: 2018-05
• Subjects: Separable convex programming -- Multiple blocks -- Parameter convergence domain -- Alternating direction method of multipliers -- Global convergence -- Complexity -- Statistical learning -- 65C60 -- 65E05 -- 68W40 -- 90C06; Mathematical optimization -- Data processing -- Periodicals; 519.6
• DOI: 10.1007/s10589-017-9971-0
• Languages: English
• ISSNs: 0926-6003

Abstract

Abstract The alternating direction method of multipliers (ADMM) has been proved to be effective for solving separable convex optimization subject to linear constraints. In this paper, we propose a generalized symmetric ADMM (GS-ADMM), which updates the Lagrange multiplier twice with suitable stepsizes, to solve the multi-block separable convex programming. This GS-ADMM partitions the data into two group variables so that one group consists ofp block variables while the other hasq block variables, where $$p \ge 1$$ p ≥ 1 and $$q \ge 1$$ q ≥ 1 are two integers. The two grouped variables are updated in aGauss–Seidel scheme, while the variables within each group are updated in aJacobi scheme, which would make it very attractive for a big data setting. By adding proper proximal terms to the subproblems, we specify the domain of the stepsizes to guarantee that GS-ADMM is globally convergent with a worst-case $${\mathcal {O}}(1/t)$$ O ( 1 / t ) ergodic convergence rate. It turns out that our convergence domain of the stepsizes is significantly larger than other convergence domains in the literature. Hence, the GS-ADMM is more flexible and attractive on choosing and using larger stepsizes of the dual variable. Besides, two special cases of GS-ADMM, which allows using zero penalty terms, are also discussed and analyzed. Compared with several state-of-the-art methods, preliminary numerical experiments on solving a sparse matrix minimization problem in the statistical learning show that our proposed method is effective and promising.