On the convergence rate of the augmented Lagrangian-based parallel splitting method. (4th March 2019) - Wang, Kai; Desai, Jitamitra
Abstract : The augmented Lagrangian method (ALM) is a well-regarded algorithm for solving convex optimization problems with linear constraints. Recently, in He et al. [ On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming, SIAM J. Optim. 25(4) (2015), pp. 2274–2312], it has been demonstrated that a straightforward Jacobian decomposition of ALM is not necessarily convergent when the objective function is the sum ofm ≥ 2 functions without coupled variables. Then, Wang et al. [ A note on augmented Lagrangian-based parallel splitting method, Optim. Lett. 9 (2015), pp. 1199–1212] proved the global convergence of the augmented Lagrangian-based parallel splitting method under the assumption that all objective functions are strongly convex. In this paper, we extend these results and derive the worst-caseO ( 1 / t ) convergence rate of this method under both ergodic and non-ergodic conditions, where t represents the number of iterations. Furthermore, we show that the convergence rate can be improved fromO ( 1 / t ) too ( 1 / t ), and finally, we also demonstrate that this method can achieve global linear convergence, when the involved functions satisfy some additional conditions.