A prediction-correction-based primal-dual hybrid gradient method for linearly constrained convex minimization
A prediction-correction-based primal-dual hybrid gradient method for linearly constrained convex minimization
复制标题
基于预测校正的线性约束凸最小化原对偶混合梯度方法
DOI：
10.1007/s11075-018-0618-8
复制
发表时间：
2019
影响因子：
2.1
通讯作者：
Gao Bin
中科院分区：
文献类型：
--
作者：
Ma Feng;Bi Yiming;Gao Bin
原始-对偶混合梯度（PDHG）方法已广泛用于解决成像处理中出现的鞍点问题。特别是，PDHG可以用来解决线性约束的凸问题。最近，它表明，没有进一步的假设，原来的PDHG可能无法收敛。在本文中，我们修改原来的PDHG得到一个收敛的方法。该方法是在一个预测-校正的方式：预测器是由PDHG和校正是由两个小的计算完成。在我们的方法中，步长参数的要求是，这与要求> Δ Δ T的一些现有的PDHG变体不同，因此允许更大的步长。我们证明了该方法的全局收敛性，并建立了O（1/t）非遍历收敛速度的结果（表示迭代次数）。数值结果表明，我们的方法与更大的步长需要更少的迭代比现有的有效的方法，以达到相同的精度。
The primal–dual hybrid gradient (PDHG) method has been widely used for solving saddle point problems emerged in imaging processing. In particular, PDHG can be used to solve convex problems with linear constraints. Recently, it was shown that without further assumptions, the original PDHG may fail to converge. In this paper, we modify the original PDHG to obtain a convergent method. The method is in a prediction–correction fashion: the predictor is generated by PDHG and the correction is completed by two minor computations. The requirement of the step size parameters in our method is, which differs from some existing PDHG variants that requirers> ∥ATA∥, and hence allows for larger step sizes. We prove the global convergence and establish theO(1/t) nonergodic convergence rate result for the method (trepresents the iteration number). Numerical results show that our method with larger step sizes needs less iterations than existing efficient methods to achieve the same accuracy.