FoCM 2014 conference
Workshop B3 - Continuous Optimization - Semi-plenary talk
December 16, 14:35 ~ 15:25 - Room A21
Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
Benjamin Recht
University of California, Berkeley, USA - brecht@berkeley.edu
I will present a new method to analyze and design iterative optimization algorithms built on the framework of Integral Quadratic Constraints (IQC) from robust control theory. IQCs provide sufficient conditions for the stability of complicated interconnected systems, and these conditions can be checked by semidefinite programming. I will discuss how to adapt IQC theory to study optimization algorithms, proving new inequalities about convex functions. Using these inequalities, I will derive upper bounds on convergence rates for the gradient method, the heavy-ball method, Nesterov's accelerated method, and related variants by solving small, simple semidefinite programming problems. I will close with a discussion of how these techniques can be used to search for optimization problems with desired performance characteristics, establishing a new methodology for algorithm design.
Joint work with Laurent Lessard (University of California, Berkeley) and Andrew Packard (University of California, Berkeley).