Abstract

Finding the saddle point of a concave-convex function is a problem that has been widely studied in since the 1950s in diverse areas and forms the basis of many classes of distributed optimisation algorithms. Nevertheless, in broad classes of problems there are features that render the analysis of the asymptotic behaviour of saddle-point dynamics nontrivial. In particular, even though for a strictly concave-convex function convergence to a saddle-point via gradient dynamics is ensured, when this strictness is lacking, convergence is not guaranteed and oscillatory solutions can occur. Furthermore, when the subgradient method is used to restrict the dynamics in a convex domain, the dynamics become non-smooth in continuous time, thus increasing significantly the complexity in the analysis.

In this talk we provide an explicit characterization to the asymptotic behaviour of gradient dynamics for saddle-point problems. In particular, we show that despite the nonlinear and non-smooth character of these dynamics their omega-limit set is comprised of trajectories that solve only linear ODEs that can be explicitly characterized. These results are used to formulate corresponding convergence criteria and various examples will also be discussed.