Please join the Simons Foundation and our generous member organizations in supporting wnyrails.org during our giving campaign September 23-27. 100% of your contribution will fund improvements and new initiatives to benefit wnyrails.org”s global scientific community.
Đang xem: Integral quadratic constraints
All fields Title Author Abstract Comments Journal reference ACM classification MSC classification Report number wnyrails.org identifier DOI ORCID wnyrails.org author ID Help pages Full text
Download PDF Abstract: 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.
|Comments:||The previous version of this paper quoted the wrong rate of Nesterov”s optimal method when applied to strongly convex functions. With this correction, our bounds are now slightly better than those previously derived for Nesterov”s method|
|Subjects:||Optimization and Control (math.OC); Systems and Control (eess.SY); Numerical Analysis (math.NA)|
From: Laurent Lessard