Lyapunov Functions

Lyapunov functions are an extremely convenient device for proving that a dynamical system converges. We cover:

  • The Lyapunov argument
  • La Salle’s Invariance Principle
  • An Alternative argument for Convex Functions
  • Exponential Convergence Rates

  • For some continuous function f:{\mathbb R}^n\rightarrow {\mathbb R}^n, we suppose x(t) obeys the differential equation
  • A Lyapunov function is a continuously differentiable function L:{\mathbb R}^n\rightarrow {\mathbb R} with unique minimum at x^* such that

  • We add the additional assumption that \{x: L(x)\leq l\} is a compact set for every l\in{\mathbb R}.

Theorem 1. If a Lyapunov exists for differential equation then L(x(t))\searrow L(x^*) as t\rightarrow\infty and

Proof. Firstly,

So L(x(t)) is decreasing. Suppose it decreases to \tilde{L}. By the Fundamental Theorem of Calculus

Thus we can take a sequence of times \{s_k\}_{k=1}^\infty such that \frac{d L(x(s_k))}{dt}\rightarrow 0 as s_k\rightarrow\infty. As \{ x : L(x)< L(x(0))\} is compact, we can take a subsequence of times \{t_k\} _{k=1}^\infty\subset \{s_k\}_{k=1}^\infty, t_k\rightarrow\infty such that \{x(t_k)\}_{k=0}^\infty converges. Suppose it converges to \tilde{x}. By continuity,

Thus by definition \tilde{x}=x^*. Thus \lim_{t\rightarrow\infty} L(x(t))=L(x^*) and thus by continuity of L at x^* we must have x(t)\rightarrow x^* QED.

  • One can check this proof follows more-or-less unchanged if x^*, the minimum of L, is not unique.

La Salle’s Invariance Principle

We generalize and strengthen the Lyapunov convergence result in Theorem 1. Here we no longer consider convergence to a unique global minimum of L(x). Instead, we find convergence to points The set \mathcal X^\star is called the set of invariant points. Notice, under the conditions of Theorem 1, \mathcal X^\star = \{ x^\star\}. In general, \mathcal X^\star contains all local [and global] minima of L(x). If the dynamics exclude invariant points which are non-local minima [for instance by taking g(x) = -\eta \nabla L(x)] then \mathcal X^\star is exactly the set of local minima. The result which proves convergence to invariant points is called Salle’s Invariance Prinicple.

We assume the following

  • The process x(t), t\in\mathbb R_+ obeys the o.d.e.

for g:\mathbb R^d \rightarrow \mathbb R^d a continuous function.

  • x(0)\in \mathcal X where \mathcal X is a compact set such that if x(0)\in \mathcal X then x(t) \in \mathcal X for all t.
  • The Lyapunov function L:\mathbb R^d \rightarrow \mathbb R_+ is a continuously differentiable function such that

  • and we let

La Salle’s Invariance Prinicple is as follows1

Theorem 2. [La Salle’s Invariance Prinicple] As t\rightarrow \infty, x(t) convergences to \mathcal X^\star uniformly over initial conditions x(0)\in \mathcal X. That is: \forall x(0) \in \mathcal X \forall \epsilon >0 \exists\; T>0 such that

Proof. If x(0) belongs to a compact set then L(x(0)) \leq l for some l\geq 0. For \delta >0, we let \mathcal X^\star(\delta)= \{x\in \mathcal X : -g(x) \cdot \nabla L(x) < \delta \}. Since dL/dt = g(x) \cdot \nabla L(x) and L(x_0)\leq l, for time T > L/\delta is must be that x(t)\in \mathcal X^\star(\delta) for all t\geq T. [This is the main part of the argument completed.]

It is reasonable to assume that x(t)\in \mathcal X^\star(\delta) for \delta suitably small then x(t) must be close to \mathcal X^\star. This is true and to show this we prove the following claim: for \epsilon >0 \exists \delta>0 such that if x(t) \in \mathcal X^\star (\delta) then |x(T) - x^\star| < \epsilon for some x^\star \in \mathcal X^\star. The proof is a fairly standard analysis argument: suppose the claim is not true, then there exists a sequence x_n such that -g(x_n) \cdot \nabla L(x_n) < 1/n and |x_n - x^\star| \geq \epsilon for all x^\star \in \mathcal X^\star. Since \mathcal X is compact x_{n_k} \rightarrow x_\infty over some subsequence \{n_k\}_{k\in\mathbb N}. By continuity g(x_\infty) \cdot \nabla L(x_\infty) =0 and |x_\infty - x^\star |\geq \epsilon for all x^\star \in \mathcal X, which is a contradiction since g(x_\infty) \cdot \nabla L(x_\infty) =0 means x_\infty \in \mathcal X^\star. This contradiction thus such thata there there exists a value n^\star such that for all x such that -g(x)\cdot \nabla L(x) < \delta := 1/n^\star implies \min_{x^\star} | x-x^\star| < \epsilon. QED.

Remark. We assume x(t) \in \mathcal X for some compact set \mathcal X. Notice a natural condition that implies compactness is that

Specifically this implies that \mathcal X_l := \{ x : L(x) \leq l\} is compact and by assumption that L(x) is decreasing, if x(0) \in \mathcal X_l then x(t)\in X_l for all t\in \mathbb R_+.


Convex Lyapunov Functions

Next if we assume a bit more about L(x) we can ask more about the rate of convergence. We assume that

  • L(x) is convex, \min_x L(x)=0
  • \frac{dx}{dt}=-\gamma_t \nabla L(x(t))
  • ||x_t||\leq D for some D

Note, before we proceed recall that L(x) is a convex function iff

Theorem 3. Given the assumptions itemized above,

where \bar x_T = \frac{1}{T}\int_{0}^{T} x_t dt.

Proof. By Jensen’s inequality,

So we analyse the integral of L(x(t)).

Notice that since \frac{dx}{dt} = -\eta_t \nabla L(x(t)) we have

Substituting this into the integral above gives

Finally, applying this to our Jensen bound on L(\bar x_T) gives

QED.


Exponential Convergence

We now place some assumptions where we can make further comments about rates of convergence.

If we further assume that f and L satisfy the conditions

  1. f(x)\cdot \nabla L(x) \leq -\gamma L(x) for some \gamma>0.
  2. \exists \alpha , \eta>0 such that \alpha || x^*-x||^\eta \leq L(x)-L(x^*).
  3. L(x^*)=0.

Theorem 5. There exists a constants \kappa,K>0 such that for all t\in{\mathbb R}_+

Proof.

So long as x(t) \neq x^*, L(x(t))>0, thus dividing by L(x(t)) and integrating gives

Rearrganging gives

This gives exponential convergence in L(x(t)) and quick application of the bound in the 2nd assumption gives

QED.

  • We can assume the 2nd assumption only holds on a ball arround x^*. We have convergence from Theorem [Lya:ConvThrm], so when x(t) is such that assumption 2 is satisfied we can then apply the same analysis for an exponential convergence rate. Ensuring the 2nd assumption locally is more easy to check, eg. check L is positive definite at x^*.

References

The Lyapunov method goes back to Lyapunov in (1892). Extensions were considered by La Salle. A widely used textbook treatment is Khalil. Applications to internet congestion control are given by Srikant. Theorem 3 is a differential equation version of the proof of Zinkevich (2003).

H. Khalil. Nonlinear Systems. Pearson Education. Prentice Hall, 2002. ISBN 9780130673893.

J. LaSalle. Some extensions of liapunov’s second method. IRE Transactions on circuit theory, 7(4):520–527, 1960.

A. M. Lyapunov. The general problem of the stability of motion. International journal of control, 55(3):531–534, 1992.

R. Srikant. The mathematics of Internet congestion control. Springer Science & Business Media, 2012.

Zinkevich, M. (2003). Online Convex Programming and Generalized Infinitesimal Gradient Ascent. ICML, 928–936.


  1. The original result of La Salle proves point-wise convergence rather than uniform convergence, other than this the proof closely follows La Salle’s argument.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s