# 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.