New convergence analysis of a primal-dual algorithm with large stepsizes
New convergence analysis of a primal-dual algorithm with large stepsizes
复制标题
DOI：
10.1007/s10444-020-09840-9
复制
发表时间：
2021-01
影响因子：
1.7
通讯作者：
Zhi Li;Ming Yan
中科院分区：
文献类型：
--
作者：
Zhi Li;Ming Yan
本文考虑一个Fréchet可微函数和极小化函数的原-对偶算法。这种原始-对偶算法在文献中有两个名称：基于邻近算子的原始-对偶固定点算法（PDFP 2 O）和邻近交替预测-校正算法（PAPC）。在本文中，我们证明了它的收敛性的步长比现有的一个较弱的条件。在附加的假设下，证明了算法的线性收敛性.此外，我们证明了这个条件（步长的上界）是紧的，不能削弱。这一结果也恢复了最近提出的正不定线性增广拉格朗日方法。此外，我们将这一结果应用到一个分散的共识算法PG-EXTRA，并推导出最弱收敛条件。
We consider a primal-dual algorithm for minimizingwith Fréchet differentiablefandl∗. This primal-dual algorithm has two names in literature: Primal-Dual Fixed-Point algorithm based on the Proximity Operator (PDFP2O) and Proximal Alternating Predictor-Corrector (PAPC). In this paper, we prove its convergence under a weaker condition on the stepsizes than existing ones. With additional assumptions, we show its linear convergence. In addition, we show that this condition (the upper bound of the stepsize) is tight and can not be weakened. This result also recovers a recently proposed positive-indefinite linearized augmented Lagrangian method. In addition, we apply this result to a decentralized consensus algorithm PG-EXTRA and derive the weakest convergence condition.