A new prediction-correction primal-dual hybrid gradient algorithm for
solving convex minimization problems with linear constraints
Abstract
The primal-dual hybrid gradient (PDHG) algorithm has been applied for
solving linearly constrained convex problems. However, it was shown
that without some additional assumptions, convergence may fail. In
this work, we propose a new competitive prediction-correction
primal-dual hybrid gradient algorithm to solve this kind of problem.
Under some conditions, we prove the global convergence for the proposed
algorithm with the rate of $O(1/N)$ in a nonergodic sense.
Comparative performance analysis of our proposed approach with other
related methods on some matrix completion and wavelet-based image
inpainting test problems shows the outperformance of our approach, in
terms of iteration number and CPU time.