Practical proximal primal-dual algorithms for structured saddle point problems

In this paper, we are concerned with a class of convex-concave saddle point problems, where one of the objective parts is assumed to be a convex and smooth function with Lipschitz continuous gradient. By exploiting the bilinear structure of the objective, we first propose a practical accelerated Proximal Primal-Dual algorithm (PPD+), which possesses an $$O(1/N^2)$$ O ( 1 / N 2 ) convergence rate measured by the residual between two successive iterates, where N represents the iteration counter. In some cases, considering that the underlying subproblems of PPD+ cannot be easily solved exactly or up to a high precision, we further propose two inexact versions of the PPD+ under absolute and relative error criteria. Finally, we employ a restarting technique to enhance our algorithms for the purpose of making them more robust and efficient. A series of numerical experiments demonstrate that our algorithms perform well in practice.