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

摘要

The Jacobian decomposition and the Gaussa??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 (lpha in(0,2-sqrt{2})) which is much less restricted than the step sizes in similar methods. Furthermore, we show that (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.