Fast convergence of the primal-dual dynamical system and algorithms for a nonsmooth bilinearly coupled saddle point problem

\(\) This paper is devoted to study the convergence rates of a second-order dynamical system and its corresponding discretizations associated with a nonsmooth bilinearly coupled convex-concave saddle point problem. We derive the convergence rate of the primal-dual gap for the second-order dynamical system with asymptotically vanishing damping term. Based on the implicit discretization, we propose a primal-dual algorithm and show the non-ergodic convergence rate under a general setting for the inertial parameters when one objective function is a continuously differentiable convex function
and another one is a proper, convex and lower semicontinuous function. We present the \( O\left(1/k^2 \right) \) convergence rate under three classical rules proposed by Nesterov, Chambolle-Dossal and Attouch-Cabot without the strong convexity, which is compatible with the results of the continuous-time dynamic system.
We further present a primal-dual algorithm based on the explicit discretization when both objective functions are continuously differentiable convex functions.
We show the corresponding non-ergodic convergence rate and prove that the sequence of iterates generated by the primal-dual algorithm weakly converges to a primal-dual optimal solution.

Article

Download

View PDF