- A search direction inspired primal-dual method for saddle point problems Shengjie Xu (xsjnsu163.com) Abstract: The primal-dual hybrid gradient algorithm (PDHG), which is indeed the Arrow-Hurwicz method, has been widely used in image processing areas. However, the convergence of PDHG was established only under some restrictive conditions in the literature, and it is still missing for the case without extra constraints. In this paper, from a perspective of the variational inequality, we show the original PDHG can provide some descend directions to the solution set. Such a fact naturally captures the line search method in optimization. Furthermore, inspired by Newton's method, we present a reversible PDHG to solve saddle point problems. Compared with the original PDHG, each iteration of the new method needs only an additional simple correction step. Moreover, we establish its global convergence and a worst-case $\mathcal{O}(1/t)$ convergence rate. Extensive numerical experiments, including several examples of image inpainting, demonstrate the efficient performance of this novel method. Keywords: convex optimization, variational inequality, saddle point problem, primal-dual hybrid gradient method, convergence rate, image restoration Category 1: Convex and Nonsmooth Optimization Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Download: [PDF]Entry Submitted: 11/24/2019Entry Accepted: 11/25/2019Entry Last Modified: 12/07/2019Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.