This manuscript develops a new framework to analyze and design iterativeoptimization algorithms built on the notion of Integral Quadratic Constraints(IQC) from robust control theory. IQCs provide sufficient conditions for thestability of complicated interconnected systems, and these conditions can bechecked by semidefinite programming. We discuss how to adapt IQC theory tostudy optimization algorithms, proving new inequalities about convex functionsand providing a version of IQC theory adapted for use by optimizationresearchers. Using these inequalities, we derive numerical upper bounds onconvergence rates for the gradient method, the heavy-ball method, Nesterov'saccelerated method, and related variants by solving small, simple semidefiniteprogramming problems. We also briefly show how these techniques can be used tosearch for optimization algorithms with desired performance characteristics,establishing a new methodology for algorithm design.
展开▼
