Stability and Instability in Saddle Point Dynamics—Part I
Stability and Instability in Saddle Point Dynamics—Part I
复制标题
鞍点动力学的稳定性和不稳定性——第一部分
DOI：
--
复制
发表时间：
2017
影响因子：
6.8
通讯作者：
Ioannis Lestas
中科院分区：
文献类型：
--
作者：
Thomas Holding;Ioannis Lestas
研究了利用梯度动力学方法研究凹凸函数收敛到鞍点的问题。自从阿罗、赫维茨和宇泽首次提出以来，这种动力学已被广泛应用于不同的领域;然而，也有一些特征使它们的分析变得重要。其中包括缺乏收敛保证时，凹凸函数考虑不满足额外的严格性和次梯度动力学的非光滑性。我们的目的是在这两个部分的文章是提供一个明确的特点，一般梯度和次梯度动力学的渐近行为适用于一般凹凸函数在$C ^2 $。我们表明，尽管这些动态的非线性和非光滑性，他们的$\omega$-极限集是由轨迹，解决只有明确的线性常微分方程的特点在这篇文章。更确切地说，在第一部分，一个精确的特征提供了无约束梯度动力学的渐近行为。我们还表明，当收敛到鞍点是不能保证的，那么系统的行为可能是有问题的，任意小的噪声导致一个无界的二阶矩的状态向量的大小。在第二部分中，我们考虑了一般类的次梯度动力学，限制轨迹在任意凸域，并表明，当一个平衡点存在，限制轨迹属于一类动力学的特征在于在第一部分线性常微分方程。这些结果被用来制定相应的收敛准则，并证明了与例子。
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.