Convex-Concave Interpolation and Application of PEP to Bilinear-Coupled Saddle-Point Problem

The Performance estimation problem (PEP) approach reformulates finding the exact worst-case performance of an algorithm as the solution to an optimization problem. Tractable formulation of the problem requires necessary and sufficient interpolation conditions. We present the interpolation conditions for convex–concave functions, bilinear functions, and composite functions with bilinear coupling. We also construct PEP for first-order methods for composite saddle-point problem.