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 , we suppose obeys the differential equation
- A Lyapunov function is a continuously differentiable function with unique minimum at such that
- We add the additional assumption that is a compact set for every .
Theorem 1. If a Lyapunov exists for differential equation then as and
So is decreasing. Suppose it decreases to . By the Fundamental Theorem of Calculus
Thus we can take a sequence of times such that as . As is compact, we can take a subsequence of times , such that converges. Suppose it converges to . By continuity,
Thus by definition . Thus and thus by continuity of at we must have QED.
- One can check this proof follows more-or-less unchanged if , the minimum of , 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 . Instead, we find convergence to points The set is called the set of invariant points. Notice, under the conditions of Theorem 1, . In general, contains all local [and global] minima of . If the dynamics exclude invariant points which are non-local minima [for instance by taking ] then 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 , obeys the o.d.e.
for a continuous function.
- where is a compact set such that if then for all .
- The Lyapunov function 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 , convergences to uniformly over initial conditions . That is: such that
Proof. If belongs to a compact set then for some . For , we let . Since and , for time is must be that for all . [This is the main part of the argument completed.]
It is reasonable to assume that for suitably small then must be close to . This is true and to show this we prove the following claim: for such that if then for some . The proof is a fairly standard analysis argument: suppose the claim is not true, then there exists a sequence such that and for all . Since is compact over some subsequence . By continuity and for all , which is a contradiction since means . This contradiction thus such thata there there exists a value such that for all such that implies . QED.
Remark. We assume for some compact set . Notice a natural condition that implies compactness is that
Specifically this implies that is compact and by assumption that is decreasing, if then for all .
Convex Lyapunov Functions
Next if we assume a bit more about we can ask more about the rate of convergence. We assume that
- is convex,
- for some
Note, before we proceed recall that is a convex function iff
Theorem 3. Given the assumptions itemized above,
Proof. By Jensen’s inequality,
So we analyse the integral of .
Notice that since we have
Substituting this into the integral above gives
Finally, applying this to our Jensen bound on gives
We now place some assumptions where we can make further comments about rates of convergence.
If we further assume that and satisfy the conditions
- for some .
- such that .
Theorem 5. There exists a constants such that for all
So long as , , thus dividing by and integrating gives
This gives exponential convergence in and quick application of the bound in the 2nd assumption gives
- We can assume the 2nd assumption only holds on a ball arround . We have convergence from Theorem [Lya:ConvThrm], so when 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 is positive definite at .
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.
- 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.↩