Sun Min, Wang Yiju
1School of Mathematics and Statistics, Zaozhuang University, Zaozhuang, P.R. China.
2School of Management, Qufu Normal University, Qufu, P.R. China.
J Inequal Appl. 2018;2018(1):269. doi: 10.1186/s13660-018-1863-z. Epub 2018 Oct 4.
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 which is much less restricted than the step sizes in similar methods. Furthermore, we show that 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.
增广拉格朗日方法（ALM）的雅可比分解和高斯-赛德尔分解是可分凸规划的两种常用方法。然而，对于三块可分凸规划，它们的收敛性无法保证。在本文中，我们提出了一种用于三块可分凸规划的改进混合分解的ALM（MHD-ALM），它首先通过ALM的混合分解更新所有变量，然后通过具有恒定步长的校正步骤校正输出，该步长比类似方法中的步长限制少得多。此外，我们证明了该恒定步长的最优上界。通过理论分析证明了MHD-ALM的合理性，包括全局收敛性、遍历收敛速率、非遍历收敛速率和精细遍历收敛速率。MHD-ALM被应用于解决视频背景提取问题，数值结果表明它在数值上是可靠的，并且计算量较小。
