Optimization Online


On the Convergence of Multi-Block Alternating Direction Method of Multipliers and Block Coordinate Descent Method

Caihua Chen (chchen***at***nju.edu.cn)
Min Li (limin***at***seu.edu.cn)
Xin Liu (liuxin***at***lsec.cc.ac.cn)
Yinyu Ye (yyye***at***stanford.edu)

Abstract: The paper answers several open questions of the alternating direction method of multipliers (ADMM) and the block coordinate descent (BCD) method that are now wildly used to solve large scale convex optimization problems in many fields. For ADMM, it is still lack of theoretical understanding of the algorithm when the objective function is not separable across the variables. In this paper, we analyze the convergence of the 2-block ADMM for solving the linearly constrained convex optimization with coupled quadratic objective, and show that the classical ADMM point-wisely converges to a primal-dual solution pair of this problem. Moreover, we propose to use the randomly permuted ADMM (RPADMM) to solve the nonseparable multi-block convex optimization, and prove its expected convergence while applied to solve a class of quadratic programming problems. When the linear constraint vanishes, the 2-block ADMM and the randomly permuted ADMM reduce to the 2-block cyclic BCD method (also known as the alternating minimization method) and the EPOCHS (the randomly permuted cyclic BCD method, also known as the ôsampling without replacement" variant of randomized BCD. For simplicity, we call it EPOCHS as suggested in the survey paper of Stephen Wright). Interestingly, our study provides the first iterate convergence result of the 2-block cyclic BCD method without assuming the boundedness of the iterates. Under the same setting, the sublinear convergence rate of the function values can also be verified. Moreover, we also theoretically establish the expected iterate convergence result of the multi-block EPOCHS or convex quadratic optimization which can be regarded as one of the first iterate convergence analysis of EPOCHS. Last but not least, although random permutation is indeed to make multi-block ADMM and BCD more robust, we theoretically demonstrate that EPOCHS has a worse convergence rate than the cyclic BCD does in solving 2-block convex quadratic minimization problems. Therefore, EPOCHS should be applied in caution when solving general optimization problems.

Keywords: Alternating direction method of multipliers, Block coordinate descent method, Iterate convergence, Random permutation, Large scale optimization, Machine learning

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: 2015

Download: [PDF]

Entry Submitted: 08/01/2015
Entry Accepted: 08/01/2015
Entry Last Modified: 09/09/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society