PRECONDITIONED DOUGLAS-RACHFORD SPLITTING METHODS FOR CONVEX-CONCAVE SADDLE-POINT PROBLEMS

摘要

We propose a preconditioned version of the Douglas-Rachford splitting method for solving convex-concave saddle-point problems associated with Fenchel-Rockafellar duality. Our approach makes it possible to use approximate solvers for the linear subproblem arising in this context. We prove weak convergence in Hilbert space under minimal assumptions. In particular, various efficient preconditioners are introduced in this framework for which only a few inner iterations are needed instead of computing an exact solution or controlling the error. The method is applied to a discrete total-variation denoising problem. Numerical experiments show that the proposed algorithms with appropriate preconditioners are very competitive with existing fast algorithms including the first-order primal-dual algorithm for saddle-point problems of Chambolle and Pock.