  Primal-dual algorithms are frequently used for iteratively solving
large-scale convex optimization problems. The analysis of such algorithms is
usually done on a case-by-case basis, and the resulting guaranteed rates of
convergence can be conservative. Here we consider a class of first-order
algorithms for linearly constrained convex optimization problems, and provide a
linear matrix inequality (LMI) analysis framework for certifying worst-case
exponential convergence rates. Our approach builds on recent results for
interpolation of convex functions and linear operators, and our LMI directly
constructs a Lyapunov function certifying the guaranteed convergence rate. By
comparing to rates established in the literature, we show that our approach can
certify significantly faster convergence for this family of algorithms.
