Revisiting Parallel Splitting Augmented Lagrangian Method: Tight Convergence and Ergodic Convergence Rate

Abstract

This paper revisits the convergence and convergence rate of the parallel splitting augmented Lagrangian method, which can be used to efficiently solve the separable multi-block convex minimization problem with linear constraints. To make use of the separable structure, the augmented Lagrangian method with Jacobian-based decomposition fully exploits the properties of each function in the objective, and results in easier subproblems. The subproblems of the method can be solved and updated in parallel, thereby enhancing computational efficiency and speeding up the convergence. We further study the parallel splitting augmented Lagrangian method with a modified correction step, which shows improved performance with larger step sizes in the correction step. By introducing a refined correction step size with a tight bound for the constant step size, we establish the global convergence of the iterates and $\mathcal{O}(1/N)$ convergence rate in both the ergodic and non-ergodic senses for the new algorithm, where N denotes the iteration numbers. Moreover, we demonstrate the applicability and promising efficiency of the method with tight step size through some applications in image processing.

Keywords

Convex programming / augmented Lagrangian method / optimal step size / convergence rate