APPROXIMATE FIRST-ORDER PRIMAL-DUAL ALGORITHMS FOR SADDLE POINT PROBLEMS

We propose two approximate versions of the first-order primal-dual algorithm (PDA) to solve a class of convex-concave saddle point problems. The introduced approximate criteria are easy to implement in the sense that they only involve the subgradient of a certain function at the current iterate. The first approximate PDA solves both subproblems inexactly and adopts the absolute error criteria, which are based on non-negative summable sequences. Assuming that one of the PDA subproblems can be solved exactly, the second approximate PDA solves the other subproblem approximately and adopts a relative error criterion. The relative error criterion only involves a single parameter in the range of [0, 1), which makes the method more applicable. For both versions, we establish the global convergence and O (1/N) convergence rate measured by the iteration complexity, where N counts the number of iterations. For the inexact PDA with absolute error criteria, we show the accelerated O(1/N ²) and linear convergence rate under the assumptions that a part of the underlying functions and both underlying functions are strongly convex, respectively. Then, we prove that these inexact criteria can also be extended to solve a class of more general problems. Finally, we perform some numerical experiments on sparse recovery and image processing problems. The results demonstrate the feasibility and superiority of the proposed methods.