Title: Stability and instability in saddle point dynamics - Part I,
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 in [1] 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 function considered is not strictly
concave-convex 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. We show that despite the nonlinearity and
non-smoothness of these dynamics their $\omega$-limit set is comprised of
trajectories that solve only explicit linear ODEs that are 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 variance.
In Part II we consider a general class of subgradient dynamics that restrict
trajectories in an arbitrary convex domain, and show that their limiting
trajectories are solutions of subgradient dynamics on only affine subspaces.
The latter is a smooth class of dynamics with an asymptotic behaviour exactly
characterized in Part I, as solutions to explicit linear ODEs. These results
are used to formulate corresponding convergence criteria and are demonstrated
with several examples and applications presented in Part II.