ON FULL JACOBIAN DECOMPOSITION OF THE AUGMENTED LAGRANGIAN METHOD FOR SEPARABLE CONVEX PROGRAMMING

被引:86
作者
He, Bingsheng [1 ,2 ]
Hou, Liusheng [3 ]
Yuan, Xiaoming [4 ]
机构
[1] South Univ Sci & Technol China, Dept Math, Shenzhen, Guangdong, Peoples R China
[2] Nanjing Univ, Dept Math, Nanjing, Jiangsu, Peoples R China
[3] Nanjing Xiaozhuang Univ, Sch Math & Informat Technol, Nanjing 211117, Jiangsu, Peoples R China
[4] Hong Kong Baptist Univ, Dept Math, Hong Kong, Hong Kong, Peoples R China
关键词
convex programming; augmented Lagrangian method; Jacobian decomposition; contraction methods; convergence rate; operator splitting methods; ALTERNATING DIRECTIONS METHOD; SPLITTING METHOD; ALGORITHM;
D O I
10.1137/130922793
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The augmented Lagrangian method (ALM) is a benchmark for solving a convex minimization model with linear constraints. We consider the special case where the objective is the sum of m functions without coupled variables. For solving this separable convex minimization model, it is usually required to decompose the ALM subproblem at each iteration into m smaller subproblems, each of which only involves one function in the original objective. Easier subproblems capable of taking full advantage of the functions' properties individually could thus be generated. In this paper, we focus on the case where full Jacobian decomposition is applied to ALM subproblems, i.e., all the decomposed ALM subproblems are eligible for parallel computation at each iteration. For the first time, we show, by an example, that the ALM with full Jacobian decomposition could be divergent. To guarantee the convergence, we suggest combining a relaxation step and the output of the ALM with full Jacobian decomposition. A novel analysis is presented to illustrate how to choose refined step sizes for this relaxation step. Accordingly, a new splitting version of the ALM with full Jacobian decomposition is proposed. We derive the worst-case O(1/k) convergence rate measured by the iteration complexity (where k represents the iteration counter) in both the ergodic and nonergodic senses for the new algorithm. Finally, some numerical results are reported to show the efficiency of the new algorithm.
引用
收藏
页码:2274 / 2312
页数:39
相关论文
共 37 条
[1]  
Boyd S., 2011, FOUND TRENDS MACH LE, V3, P1, DOI DOI 10.1561/2200000016
[2]  
Chen SSB, 2001, SIAM REV, V43, P129, DOI [10.1137/S003614450037906X, 10.1137/S1064827596304010]
[3]   Compressed sensing [J].
Donoho, DL .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (04) :1289-1306
[4]   ON THE DOUGLAS-RACHFORD SPLITTING METHOD AND THE PROXIMAL POINT ALGORITHM FOR MAXIMAL MONOTONE-OPERATORS [J].
ECKSTEIN, J ;
BERTSEKAS, DP .
MATHEMATICAL PROGRAMMING, 1992, 55 (03) :293-318
[5]  
Eckstein J., 1994, Some Reformulations and Applications of the Alternating Direction Method of Multipliers, P115
[6]  
FACCHINEI F., 2003, SPRINGER SER OPER RE, VI
[7]  
Fukushima M., 1992, Comput. Optim. Appl, V1, P93, DOI 10.1007/BF00247655
[8]  
Gabay D., 1976, Computers & Mathematics with Applications, V2, P17, DOI 10.1016/0898-1221(76)90003-1
[9]  
Gabay D., 1983, Augmented Lagrangian Methods: Applications to the Solution of Boundary Value Problems, V15, P299
[10]  
GLOWINSKI R, 1975, REV FR AUTOMAT INFOR, V9, P41