Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints

October 31, 2014, Webb 1100

Laurent Lessard

UC Berkeley , Mechanical Engineering


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 programs. I will close with a discussion of how these techniques can be used to search for algorithms with desired performance characteristics, establishing a new methodology for algorithm design.

Speaker's Bio

Laurent Lessard received the BASc in Engineering Science at the University of Toronto and the MS and PhD degrees in Aeronautics and Astronautics from Stanford University. He is currently a postdoctoral scholar in the Berkeley Center for Control and Identification at the University of California, Berkeley. Before that, he was a LCCC postdoc in the Department of Automatic Control at Lund University. His research interests lie at the intersection of optimization and control, with an emphasis on complex or decentralized systems. Dr. Lessard received the 2013 American Automatic Control Council O. Hugo Schuck Best Paper Award.