A prediction correction based primal dual hybrid gradient method for linearly constrained convex minimization
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 rs>14ATA$rs>\frac {1}{4}|A^{T}A\ which differs from some existing PDHG variants that require rs ATA, and hence allows for larger step sizes. We prove the global convergence and establish the O(1/t) nonergodic convergence rate result for the method (t represents 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.
Numerical Algorithms