Modified hybrid decomposition of the augmented Lagrangian method with larger step size for three-block separable convex programming

Abstract

Abstract The Jacobian decomposition and the Gauss–Seidel decomposition of augmented Lagrangian method (ALM) are two popular methods for separable convex programming. However, their convergence is not guaranteed for three-block separable convex programming. In this paper, we present a modified hybrid decomposition of ALM (MHD-ALM) for three-block separable convex programming, which first updates all variables by a hybrid decomposition of ALM, and then corrects the output by a correction step with constant step size α∈(0,2−2) $\alpha \in(0,2-\sqrt{2})$ which is much less restricted than the step sizes in similar methods. Furthermore, we show that 2−2 $2-\sqrt{2}$ is the optimal upper bound of the constant step size α. The rationality of MHD-ALM is testified by theoretical analysis, including global convergence, ergodic convergence rate, nonergodic convergence rate, and refined ergodic convergence rate. MHD-ALM is applied to solve video background extraction problem, and numerical results indicate that it is numerically reliable and requires less computation.

Keywords

• The augmented Lagrangian method
• Three-block separable convex programming
• Step size
• Global convergence