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

Abstract

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.

This version revises and extends the paper published in Russian Journal of Nonlinear Dynamics (2024). It expands the section dedicated to construction of PEP for composite saddle-point problems. It focuses strictly on theoretical results, omitting the preliminary numerical data from the journal version