Title | ||
---|---|---|
SOLVING MULTIPLE-BLOCK SEPARABLE CONVEX MINIMIZATION PROBLEMS USING TWO-BLOCK ALTERNATING DIRECTION METHOD OF MULTIPLIERS |
Abstract | ||
---|---|---|
In this paper, we consider solving multiple-block separable convex minimization problems using alternating direction method of multipliers (ADMM). Motivated by the fact that the existing convergence theory for ADMM is mostly limited to the two-block case, we analyze in this paper, both theoretically and numerically, a new strategy that first transforms a multi-block problem into an equivalent two-block problem (either in the primal domain or in the dual domain) and then solves it using the standard two-block ADMM. In particular, we derive convergence results for this two-block ADMM approach to solve multi-block separable convex minimization problems, including an improved O(1/is an element of) iteration complexity result. Moreover, we compare the numerical efficiency of this approach with the standard multi-block ADMM on several separable convex minimization problems which include basis pursuit, robust principal component analysis and latent variable Gaussian graphical model selection. The numerical results show that the multiple-block ADMM, although lacks theoretical convergence guarantees, typically outperforms two-block ADMMs. |
Year | Venue | Keywords |
---|---|---|
2013 | PACIFIC JOURNAL OF OPTIMIZATION | alternating direction method of multipliers,primal splitting,dual splitting |
Field | DocType | Volume |
Convergence (routing),Discrete mathematics,Mathematical optimization,Separable space,Basis pursuit,Robust principal component analysis,Minification,Gaussian,Graphical model,Convex optimization,Mathematics | Journal | 11 |
Issue | ISSN | Citations |
SP4 | 1348-9151 | 27 |
PageRank | References | Authors |
1.09 | 13 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Xiangfeng Wang | 1 | 280 | 21.75 |
Mingyi Hong | 2 | 1533 | 91.29 |
Shiqian Ma | 3 | 1068 | 63.48 |
Zhi-Quan Luo | 4 | 872 | 77.72 |