Speaker: Justin Le.
Host: Yahoo Research.
July 8, 2021 (virtual)
2pm Eastern Time
Abstract
Modern optimization problems must often be solved in an iterative feedback loop involving complex interactions between decision-making agents, technological infrastructure, and physical assets. Examples arise in robotic/vehicular systems, Internet commerce, and societal-scale systems such as networks for electrical power, transportation, communication, and water. There is an increasing need for optimization algorithms that can adaptively cope with lag, noise, uncertainty, and frequent changes in objectives or constraints, among other practical challenges that are typical in these settings. In this talk, we illustrate the design and analysis of such algorithms using tools from the stability theory of feedback control systems, which enable the combination of real-time data with model-based principles. First, we describe a systems-theoretic model for the class of so-called “dynamic” optimization problems of interest: problems having time-varying specifications and a latency between decision and outcome. Then, we focus on some special cases in which gradient methods are known to be effective, in order to illustrate how ideas from nonlinear stability theory provide guidance on tuning algorithmic parameters to achieve various performance goals pertaining to efficiency and robustness. We describe how the related stability theory of hybrid dynamical systems has recently inspired new adaptive tuning procedures that improve on certain performance metrics of practical interest in online optimization applications. Finally, we discuss the concept of input-to-state stability and its use in designing online optimization strategies with consideration of both asymptotic and transient performance. Throughout, we highlight opportunities and challenges in extending the presented ideas beyond the realm of gradient methods.