  


On the Convergence of MultiBlock Alternating Direction Method of Multipliers and Block Coordinate Descent Method
Caihua Chen (chchennju.edu.cn) 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 2block ADMM for solving the linearly constrained convex optimization with coupled quadratic objective, and show that the classical ADMM pointwisely converges to a primaldual solution pair of this problem. Moreover, we propose to use the randomly permuted ADMM (RPADMM) to solve the nonseparable multiblock convex optimization, and prove its expected convergence while applied to solve a class of quadratic programming problems. When the linear constraint vanishes, the 2block ADMM and the randomly permuted ADMM reduce to the 2block 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 2block 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 multiblock 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 multiblock ADMM and BCD more robust, we theoretically demonstrate that EPOCHS has a worse convergence rate than the cyclic BCD does in solving 2block 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  