Chebyshev polynomials meet Nevanlinna-Pick interpolation: An automated procedure for algorithm synthesis

The synthesis of optimization algorithms typically follows a design-first-analyze-later paradigm, a practice that often obscures fundamental performance limits and hampers the systematic design of algorithms operating near these limits. In this paper, we build on a recently proposed frequency-domain control framework that enables a principled approach to algorithm design, integrating the analysis and synthesis stages and thereby elucidating the fundamental performance boundaries. Specifically, we remove restrictive assumptions from recent prior work and extend the framework to encompass a broad class of strongly convex problems with equality constraints. This leads to a new family of algorithms that achieves a sharp trade-off between the number of matrix–vector multiplications per iteration and the convergence rate. Notably, one of the resulting algorithms attains the optimal lower bound on the total number of matrix-vector multiplications required to reach a prescribed accuracy.