Interpolation Conditions for Linear Operators and Applications to Performance Estimation Problems

The performance estimation problem methodology makes it possible to determine theexact worst-case performance of an optimization method. In this work, we generalize this frameworkto first-order methods involving linear operators. This extension requires an explicit formulationof interpolation conditions for those linear operators. We consider the class of linear operators\scrM : x \mapsto \rightarrow M x, where matrix M has bounded singular values, and the class of linear operators, whereM is symmetric and has bounded eigenvalues. We describe interpolation conditions for these classes,i.e., necessary and sufficient conditions that, given a list of pairs \{ (xi, yi)\} , characterize the existenceof a linear operator mapping xi to yi for all i. Using these conditions, we first identify the exactworst-case behavior of the gradient method applied to the composed objective h \circ \scrM , and observethat it always corresponds to \scrM being a scaling operator. We then investigate the Chambolle--Pock method applied to f + g \circ \scrM , and improve the existing analysis to obtain a proof of the exactconvergence rate of the primal-dual gap. In addition, we study how this method behaves on Lipschitzconvex functions, and obtain a numerical convergence rate for the primal accuracy of the last iterate.We also show numerically that averaging iterates is beneficial in this setting.