Fast convergence of inertial primal-dual dynamics and algorithms for a bilinearly coupled saddle point problem

This paper is devoted to study the convergence rates of a second-order dynamical system and its corresponding discretization associated with a continuously differentiable bilinearly coupled convex-concave saddle point problem. First, we consider the second-order dynamical system with asymptotically vanishing damping term and show the existence and uniqueness of the trajectories as global twice continuously differentiable solutions. We derive the convergence rate for the primal-dual gap along the generated trajectories for all damping coefficients $\alpha> 0$ and prove that the primal-dual trajectory of the second-order dynamical system asymptotically weakly converges to a primal-dual optimal solution of the original saddle point problem when $\alpha>3$. In addition, we obtain a faster convergence rate for the second-order dynamical system with the assumption of strongly convexity. Second, we develop the corresponding inertial algorithm which results from the discretization of the dynamical system and prove convergence properties for the primal-dual gap and the sequence of iterates. We show that the sequence of iterates generated by the inertial algorithm weakly converges to a primal-dual optimal solution which is compatible with the fact in the continuous setting.

Article

Download

View PDF