Revisiting Parallel Splitting Augmented Lagrangian Method: Tight Convergence and Ergodic Convergence Rate (CSIAM Transactions on Applied Mathematics, 2024)
This paper revisits the convergence and convergence rate of the parallelsplitting augmented Lagrangian method, which can be used to efficiently solve theseparable multi-block convex minimization problem with linear constraints. To makeuse of the separable structure, the augmented Lagrangian method with Jacobian-baseddecomposition 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 theconvergence. We further study the parallel splitting augmented Lagrangian methodwith a modified correction step, which shows improved performance with larger stepsizes in the correction step. By introducing a refined correction step size with a tightbound for the constant step size, we establish the global convergence of the iteratesand $\mathcal{O}(1/N)$ convergence rate in both the ergodic and non-ergodic senses for the newalgorithm, where $N$ denotes the iteration numbers. Moreover, we demonstrate the applicability and promising efficiency of the method with tight step size through someapplications in image processing.
Keywords: Convex programming; augmented Lagrangian method; optimal step size; convergence rate.