CUED Publications database

Stability and instability in saddle point dynamics - Part I

Holding, T and Lestas, I Stability and instability in saddle point dynamics - Part I. IEEE Transactions on Automatic Control. ISSN 0018-9286 (Unpublished)

Full text not available from this repository.

Abstract

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 non trivial. These include the lack of convergence guarantees when the concave-convex function considered does not satisfy additional strictness properties and also the non-smoothness of subgradient dynamics. Our aim in this two part paper is to provide an explicit characterization to the asymptotic behaviour of general gradient and subgradient dynamics applied to a general concave-convex function in $C^2$ . We show that despite the nonlinearity and non-smoothness of these dynamics their ω-limit set is comprised of trajectories that solve only explicit linear ODEs characterized within the paper. More precisely, in Part I an exact characterization is provided to the asymptotic behaviour of unconstrained gradient dynamics. We also show that when convergence to a saddle point is not guaranteed then the system behaviour 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.

Item Type: Article
Uncontrolled Keywords: math.OC math.OC cs.SY eess.SY
Subjects: UNSPECIFIED
Divisions: Div F > Control
Depositing User: Cron Job
Date Deposited: 22 Aug 2020 20:11
Last Modified: 02 Sep 2021 05:52
DOI: 10.1109/TAC.2020.3019375