Tight Lower Bounds on the Convergence Rate of Primal-Dual Dynamics for Equality Constrained Convex Problems

We study the exponential stability of continuous-time primal-dual gradient flow dynamics for convex optimization problems with linear equality constraints. Without making any assumptions on the rank of the constraint matrix, we obtain a tight lower bound on the worst-case convergence rate for smooth strongly convex objective functions. Our analysis identifies two different convergence regimes depending on the ratio between primal and dual time scales. When the primal time scale is inversely proportional to the Lipschitz parameter of the objective function and the dual time scale is large enough, the convergence rate is inversely proportional to the condition number of the problem. In contrast to the existing results, our lower bound on the convergence rate does not depend on the condition number of the constraint matrix.