Inertial Primal Dual Dynamics with Hessian-driven Damping for Saddle Point Problems

Abstract

Featuring Hessian-driven damping, two inertial primal dual dynamical systems are proposed for solving smooth saddle point problems with bilinear coupling. For convex-concave functions, we establish a convergence rate $\mathcal{O}\left(\frac{1}{t^2}\right)$ for the primal dual gap; for strongly convex-strongly concave functions, we obtain an asymptotic rate $\mathcal{O}\left(\frac{1}{t^{\hat{I}\pm -1}}\right)$ ($\hat{I}\pm \ge 3$ is the damping parameter) without knowledge of the strong convexity parameters, and an accelerated linear convergence rate when the strong convexity parameters are known. As an application of the proposed inertial systems, we also consider the affinely constrained convex optimization problem, and develop an inertial system with Hessian-driven damping, which complements existing results.

Topics & keywords