A golden ratio primal-dual algorithm.

This paper presents a golden ratio primal-dual algorithm (GRPDA) for solving convex optimization problems with known bilinear saddle-point structure, using a convex combination of all previous iterates rather than classic inertial technique. Both fixed and adaptive step sizes gained by linesearch are involved, and each iteration of the linesearch requires to update only the dual variable. The convergence and ergodic O(1/N) convergence rate for the primal-dual gap are established under two types of step sizes. In case when one of the prox-functions is strongly convex, we modify our basic method to get a better convergence rate O(1/N2). Moreover, we observe that GRPDA with fixed step sizes is an inexact Alternating Direction Method of Multipliers (ADMM) with linearization and indefinite proximal regularization. The numerical experiments illustrate the proposed PDA is efficient.