On the convergence to saddle points of concave-convex functions, the gradient method and emergence of oscillations
On the convergence to saddle points of concave-convex functions, the gradient method and emergence of oscillations
复制标题
凹凸函数收敛到鞍点、梯度法与振荡的出现
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Ioannis Lestas
中科院分区：
文献类型：
--
作者：
Thomas Holding;Ioannis Lestas
已知对于严格凹凸函数，Arrow和Hurwicz[1]引入的梯度法保证全局收敛到它的鞍点。然而，有一类问题，其中所考虑的函数不是严格的凹凸，在这种情况下，收敛到鞍点是不保证的。在本文中，我们提供了梯度方法的渐近性质的一个表征，在一般情况下，这是适用于一般凹凸函数。证明了对于任何初始条件，梯度法都保证收敛于由显式线性ODE描述的轨迹。我们进一步证明了这一结果有一个自然的推广到子梯度方法，其中动力学被约束在一个规定的凸集中。利用所得结果，给出了一类特殊优化问题的极限解的简单表征，并讨论了问题的修正以避免振荡。
It is known that for a strictly concave-convex function, the gradient method introduced by Arrow and Hurwicz [1], has guaranteed global convergence to its saddle point. Nevertheless, there are classes of problems where the function considered is not strictly concave-convex, in which case convergence to a saddle point is not guaranteed. In the paper we provide a characterization of the asymptotic behaviour of the gradient method, in the general case where this is applied to a general concave-convex function. We prove that for any initial conditions the gradient method is guaranteed to converge to a trajectory described by an explicit linear ODE. We further show that this result has a natural extension to subgradient methods, where the dynamics are constrained in a prescribed convex set. The results are used to provide simple characterizations of the limiting solutions for special classes of optimization problems, and modifications of the problem so as to avoid oscillations are also discussed.