On the convergence rate of the augmented Lagrangian-based parallel splitting method

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 of $m\ge 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-case $O\left(1/t\right)$ 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 from $O\left(1/t\right)$ to $o\left(1/t\right)$, and finally, we also demonstrate that this method can achieve global linear convergence, when the involved functions satisfy some additional conditions.

Keywords:

• augmented Lagrangian method
• separable convex programming
• Jacobian decomposition
• parallel splitting method
• global linear convergence
• convergence rate

AMS Subject Classification:

• 65K05
• 90C25
• 90C30

Disclosure statement

No potential conflict of interest was reported by the authors.10.13039/501100001459

Additional information

Funding

This research was supported by Ministry of Education (Singapore) Tier 1 Grant No. M4011083.