# Algorithm to scan Lyapunov candidate functions

Let's say you are trying to establish the stability of an equilibrium point in a nonlinear system, but you are having trouble coming up with an appropriate Lyapunov function. (Or, you're lazy and don't want to do the work yourself.)

Are there any functions/algorithms (e.g. in Mathematica, Sage, or Python) for finding Lyapunov functions for any given nonlinear system? I can't seem to find any with a quick Google search, but it seems like it would be relatively simple to implement something that is very likely (maybe not 100% guaranteed) to find a Lyapunov function if one exists. Especially if the number of variables in the system is relatively small.

I'm thinking something along the lines of:

• Iterate over a list of positive definite functions $V(x)$ (e.g. quadratic forms and other polynomials).
• For each candidate function, determine if $\dot{V}$ is negative semidefinite or negative definite.
• Stop when you find a negative definite $\dot{V}$ or give up after a user-defined number of iterations

Would this work, or is this a more complicated problem than I'm making it out to be?

## 1 Answer

For nonlinear systems the Sum of Square polynomial Lyapunov function can be constructed algorithmically. See On the Construction of Lyapunov Functions using the Sum of Squares Decomposition. Basically the sos approximation constraint the polynomial optimization of finding a Lyapunov function to be a semidefinite program, which is generally considered solvable (for low dimension cases). For implementation in Matlab, see SOSTOOLS, which is a parser for constructing polynomial optimization problems. There are recent work in using so-called DSOS and SDSOS relaxation that constraints the problem further to more solvable linear programming or second-order cone programming. However, all of the above can not guarantee to find a Lyapunov function, because, first, for a global asymptotically stable ode system with polynomial vector fields, it does not necessarily have a polynomial Lyapunov function; second, for such a system that has a polynomial Lyapunov function, it does not necessarily has a Lyapunov function that can be found by SOS programming, see Pable Parrilo's work.