O(1/t) complexity analysis of the generalized alternating direction method of multipliers  

作　　者：Xingju Cai Deren Han 

机构地区：[1]School of Mathematical Sciences and Key Laboratory for Numerical Simulation of Large Scale Complex Systems of Jiangsu Province, Nanjing Normal University

出　　处：《Science China Mathematics》2019年第4期795-808,共14页中国科学：数学（英文版）

基　　金：supported by a Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions;National Natural Science Foundation of China (Grant Nos. 11401315, 11625105, 11171159 and 11431102);the National Science Foundation from Jiangsu Province (Grant No. BK20140914)

摘　　要：Owing to its efficiency in solving some types of large-scale separable optimization problems with linear constraints, the convergence rate of the alternating direction method of multipliers(ADMM for short) has recently attracted significant attention. In this paper, we consider the generalized ADMM(G-ADMM), which incorporates an acceleration factor and is more efficient. Instead of using a solution measure that depends on a bounded set and cannot be easily estimated, we propose using the original ?-optimal solution measure, under which we prove that the G-ADMM converges at a rate of O(1/t). The new bound depends on the penalty parameter and the distance between the initial point and the solution set, which is more reasonable than the previous bound.Owing to its efficiency in solving some types of large-scale separable optimization problems with linear constraints, the convergence rate of the alternating direction method of multipliers(ADMM for short) has recently attracted significant attention. In this paper, we consider the generalized ADMM(G-ADMM), which incorporates an acceleration factor and is more efficient. Instead of using a solution measure that depends on a bounded set and cannot be easily estimated, we propose using the original ?-optimal solution measure, under which we prove that the G-ADMM converges at a rate of O(1/t). The new bound depends on the penalty parameter and the distance between the initial point and the solution set, which is more reasonable than the previous bound.

关 键 词：generalized ALTERNATING direction method of MULTIPLIERS SEPARABLE CONVEX optimization ITERATION complexity SUBLINEAR convergence rate 

分 类 号：O1[理学—数学]