Stability and Instability in Saddle Point Dynamics-Part I

• 成果类型: Article
• 署名作者: Holding, Thomas; Lestas, Ioannis
• 署名单位: Imperial College London; University of Cambridge
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2020.3019375
• 发表日期: 2021
• 页码: 2933-2944
• 关键词: Gradient dynamics; large-scale systems; Nonlinear systems; optimization; saddle points

摘要

We consider the problem of convergence to a saddle point of a concave-convex function via gradient dynamics. Since first introduced by Arrow, Hurwicz, and Uzawa, such dynamics have been extensively used in diverse areas; there are, however, features that render their analysis nontrivial. These include the lack of convergence guarantees when the concave-convex function considered does not satisfy additional strictness properties and also the nonsmoothness of subgradient dynamics. Our aim in this two-part article is to provide an explicit characterization to the asymptotic behavior of general gradient and subgradient dynamics applied to a general concave-convex function in C-2. We show that despite the nonlinearity and nonsmoothness of these dynamics, their omega-limit set is comprised of trajectories that solve only explicit linear ODEs characterized within this article. More precisely, in part I, an exact characterization is provided to the asymptotic behavior of unconstrained gradient dynamics. We also show that when convergence to a saddle point is not guaranteed, then the system behavior can be problematic, with arbitrarily small noise leading to an unbounded second moment for the magnitude of the state vector. In part II, we consider a general class of subgradient dynamics that restrict trajectories in an arbitrary convex domain, and show that when an equilibrium point exists, the limiting trajectories belong to a class of dynamics characterized in part I as linear ODEs. These results are used to formulate corresponding convergence criteria and are demonstrated with examples.