On the convergence rate of the augmented Lagrangian-based parallel splitting method. (4th March 2019)

• Record Type: Journal Article
• Authors: Wang, Kai; Desai, Jitamitra
• Is Part Of: Optimization methods and software. Volume 34:Number 2(2019)
• Page Start: 278
• Page End: 304
• Publication Date: 2019-03-04
• Subjects: augmented Lagrangian method -- separable convex programming -- Jacobian decomposition -- parallel splitting method -- global linear convergence -- convergence rate; 65K05 -- 90C25 -- 90C30; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2017.1370711
• Languages: English
• ISSNs: 1055-6788

Abstract

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.