On the stable equilibrium points of gradient systems

doi:10.1016/j.sysconle.2006.01.002

Systems & Control Letters

Volume 55, Issue 7, July 2006, Pages 573-577

https://doi.org/10.1016/j.sysconle.2006.01.002 Get rights and content

Abstract

This paper studies the relations between the local minima of a cost function f and the stable equilibria of the gradient descent flow of f. In particular, it is shown that, under the assumption that f is real analytic, local minimality is necessary and sufficient for stability. Under the weaker assumption that f is indefinitely continuously differentiable, local minimality is neither necessary nor sufficient for stability.

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 $C^{\infty}$ 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 $R^{n}$ and consider the continuous-time gradient-descent system $\dot{x} (t) = - \nabla f (x (t)),$ where $\nabla f (x)$ denotes the Euclidean gradient of f at x. Define stability and minimality in the standard way:

Definition 1

A point $z \in R^{n}$ is a local minimum of f if there exists $ε > 0$ such that $f (x) ⩾ f (z)$ for all x such that $∥ x - z ∥ < ε$ . If $f (x) > f (z)$ for all x such that $0 < ∥ x - z ∥ < ε$ , then z is a strict local minimum of f. An equilibrium point z of (1) is (Lyapunov) stable if, for each $ε > 0$ , there is $δ = δ (ε) > 0$ such that $∥ x (0) - z ∥ < δ \Rightarrow ∥ x (t) - z ∥ < ε \forall t ⩾ 0 .$ It is asymptotically stable if it is stable, and $δ$ can be chosen such that $∥ x (0) ∥ < δ \Rightarrow \lim_{t \to \infty} x (t) = z$ .

Then we have:

Proposition 2

(i) There exist a function $f \in C^{\infty}$ and a point $z \in R^{n}$ such that z is a local minimum of f and z is not a stable equilibrium point of (1). (ii) There exist a function $f \in C^{\infty}$ and a point $z \in R^{n}$ 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 $z \in R^{n}$ . 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 $C^{\infty}$ and analytic cost functions. Final remarks are presented in Section 5.

Section snippets

Smooth cost function

In this section we prove Proposition 2. Consider $f : R^{n} \to R$ defined by $f (x, y) = \frac{1}{1 + x^{2}} g (y) h (y),$ where $g (y) = \{\begin{matrix} e^{- 1 / y^{2}} & if y \neq 0, \\ 0 & if y = 0, \end{matrix}$ and $h (y) = \{\begin{matrix} y^{2} + 1 + \sin \frac{1}{y^{2}} & if y \neq 0, \\ 1 & if y = 0 . \end{matrix}$ This function is qualitatively illustrated in Fig. 1. We show that this function f satisfies the properties of point (i) of Proposition 2 with $z = (0, 0)$ . It is routine to check that $f \in C^{\infty}$ , and it is clear that the origin is a local minimum of f, since f is nonnegative and $f (0) = 0$ . The gradient system (1) becomes $\dot{x} = \frac{2 x}{(1 + x^{2})^{2}} g (y) h (y),$ $\dot{y} = - \frac{1}{1 + x^{2}} \frac{g (y)}{y^{3}} m (y),$

Analytic cost function

This section is dedicated to proving Theorem 3. We assume throughout, without loss of generality, that $f : R^{n} \to R$ is analytic on an open set U containing the origin, that $f (0) = 0$ and that $\nabla f (0) = 0$ , 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 $R^{n}$ . Then there are constants $c > 0$ and $ρ \in [0, 1)$ such that $∥ \nabla f (x) ∥ ⩾ c | f (x) - f (z) |^{ρ}$ 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 $f \in C^{p}$ , $p \in {2, 3, \dots} \cup {\infty}$ , the classical way of studying the stability of an equilibrium point (say $x = 0$ ) of the gradient-descent flow (1) is to consider the Hessian of f at $x = 0$ . If the Hessian is positive definite, then $x = 0$ 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 $f (x) = x^{4}$ 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)

P.-A. Absil et al.
Continuous dynamical systems that realize discrete optimization on the hypercube
Systems Control Lett.
(2004)
D. Jiang et al.
A gradient flow approach to decentralised output feedback optimal control
Systems Control Lett.
(1996)
J.H. Manton et al.
A dual purpose principal and minor component flow
Systems Control Lett.
(2005)
D. Ridout et al.
Convergence properties of gradient descent noise reduction
Physica D
(2002)
N.T. Trendafilov et al.
The multimode Procrustes problem
Linear Algebra Appl.
(2002)
P.-A. Absil 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...
E. Bierstone 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,...

There are more references available in the full text version of this article.

Cited by (127)

Optimization algorithms as robust feedback controllers
2024, Annual Reviews in Control
Mathematical optimization is one of the cornerstones of modern engineering research and practice. Yet, throughout all application domains, mathematical optimization is, for the most part, considered to be a numerical discipline. Optimization problems are formulated to be solved numerically with specific algorithms running on microprocessors. An emerging alternative is to view optimization algorithms as dynamical systems. Besides being insightful in itself, this perspective liberates optimization methods from specific numerical and algorithmic aspects and opens up new possibilities to endow complex real-world systems with sophisticated self-optimizing behavior. Towards this goal, it is necessary to understand how numerical optimization algorithms can be converted into feedback controllers to enable robust “closed-loop optimization”. In this article, we focus on recent control designs under the name of “feedback-based optimization” which implement optimization algorithms directly in closed loop with physical systems. In addition to a brief overview of selected continuous-time dynamical systems for optimization, our particular emphasis in this survey lies on closed-loop stability as well as the robust enforcement of physical and operational constraints in closed-loop implementations. To bypass accessing partial model information of physical systems, we further elaborate on fully data-driven and model-free operations. We highlight an emerging application in autonomous reserve dispatch in power systems, where the theory has transitioned to practice by now. We also provide short expository reviews of pioneering applications in communication networks and electricity grids, as well as related research streams, including extremum seeking and pertinent methods from model predictive and process control, to facilitate high-level comparisons with the main topic of this survey.
Physics-informed deep reinforcement learning-based integrated two-dimensional car-following control strategy for connected automated vehicles
2023, Knowledge-Based Systems
Connected automated vehicles (CAVs) are broadly recognized as next-generation transformative transportation technologies having great potential to improve traffic safety, efficiency, and stability. Efficiently controlling CAVs on two-dimensional curvilinear roadways to follow preceding vehicles is denoted as the two-dimensional car-following process, which is highly critical; this process is challenging to implement owing to the complexity and varied nature of driving environments. This study proposes an innovative integrated two-dimensional control strategy for CAVs based on deep reinforcement learning (DRL), which efficiently regulates the two-dimensional car-following process of CAVs in terms of both stability-wise longitudinal control performance and accurate lateral path-tracking performance. Within the control framework, each CAV can receive the surrounding information from downstream vehicles and roadway geometry based on vehicle-to-everything (V2X) communication. To better utilize this information, we designed a physics-informed DRL state fusion approach and reward function, which efficiently embeds prior physics knowledge and borrows the merits of the equilibrium and consensus concepts from the control theory. Given the physics-informed information, the DRL-based controller outputs the integrated control instructions for both longitudinal and lateral control. For training, we constructed a roadway with a set of varying curvatures and embedded the ground-truth vehicle trajectory datasets to more effectively capture the realistic variations in the roadway geometry and driving environment. To facilitate value function approximation and enhance the policy iteration process in training, the distributed proximal policy optimization (DPPO) algorithm was applied, owing to its balanced performance. A series of simulated experiments were conducted to validate the controller’s lateral control accuracy and stability-wise oscillation dampening performance in diverse traffic scenarios, including extreme ones.
A deep reinforcement learning based distributed control strategy for connected automated vehicles in mixed traffic platoon
2023, Transportation Research Part C: Emerging Technologies
This paper proposes an innovative distributed longitudinal control strategy for connected automated vehicles (CAVs) in the mixed traffic environment of CAV and human-driven vehicles (HDVs), incorporating high-dimensional platoon information. For mixed traffic, the traditional CAV control method focuses on microscopic trajectory information, which may not be efficient in handling the HDV stochasticity (e.g., long reaction time; various driving styles) and mixed traffic heterogeneities. Different from traditional methods, our method, for the first time, characterizes consecutive HDVs as a whole (i.e., AHDV) to reduce the HDV stochasticity and utilize its macroscopic features to control the following CAVs. The new control strategy takes advantage of platoon information to anticipate the disturbances and traffic features induced downstream under mixed traffic scenarios and greatly outperforms the traditional methods. In particular, the control algorithm is based on deep reinforcement learning (DRL) to fulfill car-following control efficiency and further address the stochasticity for the aggregated car following behavior by embedding it in the training environment. To better utilize the macroscopic traffic features, a general platoon of mixed traffic is categorized as a CAV-HDVs-CAV pattern and described by corresponding DRL states. The macroscopic traffic flow properties are built upon the Newell car-following model to capture the characteristics of aggregated HDVs' joint behaviors. Simulated experiments are conducted to validate our proposed strategy. The results demonstrate that the proposed control method has outstanding performances in terms of oscillation dampening, eco-driving, and generalization capability.
Online optimization of switched LTI systems using continuous-time and hybrid accelerated gradient flows
2022, Automatica
This paper studies the design of feedback controllers to steer a switching linear dynamical system to the solution trajectory of a time-varying convex optimization problem. We propose two types of controllers: (i) a continuous controller inspired by the online gradient descent method, and (ii) a hybrid controller that can be interpreted as an online version of Nesterov’s accelerated gradient method with restarts of the state variables. By design, the controllers continuously steer the system toward a time-varying optimal equilibrium point without requiring knowledge of exogenous disturbances affecting the system. For cost functions that are smooth and satisfy the Polyak–Łojasiewicz inequality, we demonstrate that the online gradient-flow controller ensures uniform global exponential stability when the time scales of the system and controller are sufficiently separated and the switching signal of the system varies slowly on average. For cost functions that are strongly convex, we show that the hybrid accelerated controller can outperform the continuous gradient descent method. When the cost function is not strongly convex, we show that the hybrid accelerated method guarantees global practical asymptotic stability.
Łojasiewicz gradient inequalities for polynomial functions and some applications
2022, Journal of Mathematical Analysis and Applications
Let $f : R^{n} \to R$ be a non-constant polynomial function. This paper studies the existence of the following global Łojasiewicz gradient inequality and Łojasiewicz gradient inequality at infinity for $x \in R^{n}$ and for $‖ x ‖ ≫ 1$ , where $c > 0$ and $θ, μ, λ \in R$ are constants. We focus our attention on some cases where the exponents are non-negative and belong to $[0, 1)$ . Moreover, we give some applications in global optimization for the existence of these inequalities with the exponents smaller than 1.
Optimization flows landing on the Stiefel manifold
2022, IFAC-PapersOnLine
We study a continuous-time system that solves optimization problems over the set of orthonormal matrices, which is also known as the Stiefel manifold. The resulting optimization flow follows a path that is not always on the manifold but asymptotically lands on the manifold. We introduce a generalized Stiefel manifold to which we extend the canonical metric of the Stiefel manifold. We show that the vector field of the proposed flow can be interpreted as the sum of a Riemannian gradient on a generalized Stiefel manifold and a normal vector. Moreover, we prove that the proposed flow globally converges to the set of critical points, and any local minimum and isolated critical point is asymptotically stable.

View all citing articles on Scopus

^☆: 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.

View full text

On the stable equilibrium points of gradient systems☆

Abstract

Introduction

Section snippets

Smooth cost function

Analytic cost function

Strict minimality and asymptotic stability

Final remarks

Acknowledgements

Systems Control Lett.

Systems Control Lett.

Systems Control Lett.

Physica D

Linear Algebra Appl.

Convergence of the iterates of descent methods for analytic cost functions

SIAM J. Optim.

Semianalytic and subanalytic sets

Inst. Hautes Études Sci. Publ. Math.