Performance Analysis of First-order Optimization Methods Using Interpolation Conditions Without Function Evaluations

We present necessary and sufficient conditions for the interpolation of a set of points and gradient evaluations by a smooth and strongly convex function. The conditions are expressed as quadratic constraints over doubly hyperdom-inant matrices. The current literature focuses on interpolation conditions involving both gradient and function evaluations. An extension of these results to use only gradient evaluations requires factorial growth in the number of constraints. Our approach avoids the factorial growth when the interpolation conditions are applied to both finite step and asymptotic optimization algorithm analysis. We present a numerical example demonstrating that the use of these interpolation conditions in the asymptotic analysis setting can produce tighter bounds than are currently available in the literature.