On the stable equilibrium points of gradient systems☆
Introduction
Gradient flows are useful in solving various optimization-related problems. Recent examples deal with principal component analysis [21], [15], optimal control [20], [9], balanced realizations [7], ocean sampling [3], noise reduction [16], pose estimation [4] or the Procrustes problem [18]. The underlying idea is that the gradient-descent flow will converge to a local minimum of the cost function. It is, however, well known that this property does not hold in general: the initial condition can, e.g. belong to the stable manifold of a saddle point. Not as well known is the fact that, even assuming that the cost function is a function, the local minima of the cost function are not necessarily stable equilibria of the gradient-descent system, and vice versa. The main purpose of this paper is to shed some light on this issue.
Specifically, let f be a real, continuously differentiable function on and consider the continuous-time gradient-descent systemwhere denotes the Euclidean gradient of f at x. Define stability and minimality in the standard way: Definition 1 A point is a local minimum of f if there exists such that for all x such that . If for all x such that , then z is a strict local minimum of f. An equilibrium point z of (1) is (Lyapunov) stable if, for each , there is such that It is asymptotically stable if it is stable, and can be chosen such that .
Then we have: Proposition 2 (i) There exist a function and a point such that z is a local minimum of f and z is not a stable equilibrium point of (1). (ii) There exist a function and a point such that z is not a local minimum of f and z is a stable equilibrium point of (1).
The proof given in Section 2 consists in producing functions f that satisfy the required properties.
After smoothness, the next stronger condition one may think of imposing on the cost function f is real analyticity (a real function is analytic if it possesses derivatives of all orders and agrees with its Taylor series in the neighbourhood of every point). The main result of this paper is that under the analyticity assumption, local minimality becomes a necessary and sufficient condition for stability. Theorem 3 Main result Let f be real analytic in a neighbourhood of . Then, z is a stable equilibrium point of (1) if and only if it is a local minimum of f.
The proof of this theorem, given in Section 3, relies on an inequality by Łojasiewicz that yields bounds on the length of solution curves of the gradient system (1).
Moreover, we give in Section 4 a complete characterization of the relations between (isolated, strict) local minima and (asymptotically) stable equilibria for gradient flows of both and analytic cost functions. Final remarks are presented in Section 5.
Section snippets
Smooth cost function
In this section we prove Proposition 2. Consider defined bywhereand This function is qualitatively illustrated in Fig. 1. We show that this function f satisfies the properties of point (i) of Proposition 2 with . It is routine to check that , and it is clear that the origin is a local minimum of f, since f is nonnegative and . The gradient system (1) becomes
Analytic cost function
This section is dedicated to proving Theorem 3. We assume throughout, without loss of generality, that is analytic on an open set U containing the origin, that and that , and we study the stability of the equilibrium point 0 of the gradient system (1).
The proof relies on the following fundamental property of analytic functions. Lemma 4 Łojasiewicz's inequality Let f be a real analytic function on a neighbourhood of z in . Then there are constants and such that in some
Strict minimality and asymptotic stability
The previous results were concerned with (simple) Lyapunov stability and (nonstrict) minimality. In this section, we also consider asymptotic stability and strict minimality. The relations between Lyapunov stability, asymptotic stability, and various notions of minimality are displayed in Fig. 2, with the following notation (see Definition 1 for details). LM: local minimum; SLM: strict local minimum; ILM: isolated local minimum; LMICP: local minimum and isolated critical point; SE: stable
Final remarks
For a general cost function , , the classical way of studying the stability of an equilibrium point (say ) of the gradient-descent flow (1) is to consider the Hessian of f at . If the Hessian is positive definite, then is a local minimum and an isolated critical point of f (LCICP in Fig. 2); it follows from Fig. 2 that the origin is asymptotically stable. But the converse is not true, as the simple example shows (the origin is asymptotically stable but the
Acknowledgements
The authors thank A.L. Tits and R. Sepulchre for several useful comments. Part of this work was done while the first author was visiting the second author at the Laboratoire de Mathématiques de l’Université de Savoie. The hospitality of the members of the Laboratory is gratefully acknowledged.
References (21)
- et al.
Continuous dynamical systems that realize discrete optimization on the hypercube
Systems Control Lett.
(2004) - et al.
A gradient flow approach to decentralised output feedback optimal control
Systems Control Lett.
(1996) - et al.
A dual purpose principal and minor component flow
Systems Control Lett.
(2005) - et al.
Convergence properties of gradient descent noise reduction
Physica D
(2002) - et al.
The multimode Procrustes problem
Linear Algebra Appl.
(2002) - et al.
Convergence of the iterates of descent methods for analytic cost functions
SIAM J. Optim.
(2005) - R. Bachmayer, N.E. Leonard, Vehicle networks for gradient descent in a sampled environment, Proceedings of the 41st...
- M. Baeg, U. Helmke, J.B. Moore, Gradient flow techniques for pose estimation of quadratic surfaces, Proceedings of the...
- et al.
Semianalytic and subanalytic sets
Inst. Hautes Études Sci. Publ. Math.
(1988) - D. D’Acunto, K. Kurdyka, Bounds for gradient trajectories of polynomial and definable functions with applications,...
Cited by (127)
Optimization algorithms as robust feedback controllers
2024, Annual Reviews in ControlA deep reinforcement learning based distributed control strategy for connected automated vehicles in mixed traffic platoon
2023, Transportation Research Part C: Emerging TechnologiesŁojasiewicz gradient inequalities for polynomial functions and some applications
2022, Journal of Mathematical Analysis and ApplicationsOptimization flows landing on the Stiefel manifold
2022, IFAC-PapersOnLine
- ☆
This work was initiated while the first author was a Research Fellow with the Belgian National Fund for Scientific Research (Aspirant du F.N.R.S.) at the University of Liège. This work was supported in part by the School of Computational Science of Florida State University through a postdoctoral fellowship, and by Microsoft Research through a Research Fellowship at Peterhouse, Cambridge.