Lyapunov functions

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

  • 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

<img class=" aligncenter" title="\label{Lya:Lya} f(x)\cdot \nabla L(x)

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

Thrm [Lya:ConvThrm] If a Lyapunov exists for differential equation then L(x(t))\searrow L(x^*) as t\rightarrow\infty and

Proof: Firstly,

<img class=" aligncenter" title="\frac{d L(x(t))}{dt} = f(x(t))\cdot \nabla L(x(t))

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^*.

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

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.

then there exists a constants \kappa,K>0 such that for all t\in{\mathbb R}_+

 

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

  • 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^*.
Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s