On the Algorithmic Construction of Lyapunov Functions for Continuous Vector Fields

Raavi Gupta, Sameep Chattopadhyay, Pradyumna Paruchuri, Debasish ChatterjeeSSRN 2023 · DOI

TL;DR

This paper introduces a novel, numerically tractable algorithm for automatically constructing Lyapunov functions for continuous vector fields. This is a significant advancement because it provides a general method for proving the stability of equilibrium points in complex nonlinear systems, a task that has historically been challenging and often required expert intuition.

What Problem Does This Paper Address?

Lyapunov functions are a cornerstone of stability analysis in dynamical systems. They provide a way to determine if an equilibrium point of a system will remain stable (i.e., not diverge) without explicitly solving the system's differential equations. However, finding these functions, especially for nonlinear systems, is notoriously difficult. Existing methods are often limited to specific classes of systems (like linear or polynomial systems) or rely on specialized algebraic structures. This paper addresses the gap by proposing a general algorithmic approach that can handle continuous nonlinear vector fields, even when their analytical expressions are not fully known or are computationally complex.

Methods

The core of the paper's contribution lies in its algorithmic procedure for constructing Lyapunov functions. The approach involves:

  • Defining a "Candidate Lyapunov Triplet": This triplet consists of:
  • A compact neighborhood ($N_0$) around the equilibrium point.
  • A set of class K functions ($\rho_1, \rho_2, \rho_3$) that define the desired properties of the Lyapunov function (positive definiteness, decrescence, and stability margin).
  • Dictionaries ($D_V, D_W$) of linearly independent, continuously differentiable functions from which the candidate Lyapunov function ($V$) and a stability margin function ($W$) are constructed.
  • Formulating a Convex Semi-Infinite Program (SIP): The problem of finding a suitable Lyapunov function is recast into a convex SIP. This program involves an infinite number of constraints that must be satisfied over the chosen neighborhood $N_0$.
  • Solving the SIP via a Max-Min Problem: The authors leverage recent results ([DACC22]) to transform the SIP into a tractable max-min problem. This involves finding a set of "critical points" within the neighborhood $N_0$ that, when considered, effectively reduce the infinite constraints to a finite set.
  • Finitely Constrained Convex Optimization: The max-min problem is then further reduced to a standard, finitely constrained convex optimization problem. This problem is solved numerically to find the coefficients of the candidate Lyapunov function.

A key novelty is that the algorithm does not require the analytical expression of the vector field $f$; it only needs the ability to evaluate $f$ at any given point.

Datasets

Not discussed in the paper. The paper focuses on developing a general algorithmic method and demonstrates its application through various numerical examples of known dynamical systems.

Key Insights and Ideas

  • Algorithmic Generality: The most significant insight is the development of a general algorithmic framework for Lyapunov function construction that is not tied to specific system structures (linear, polynomial) or algebraic properties.
  • Bridging Theory and Practice: The paper successfully bridges the theoretical gap in finding Lyapunov functions by translating the problem into a numerically solvable optimization framework.
  • No Analytical Expression Needed: The ability to construct Lyapunov functions without knowing the explicit analytical form of the vector field is a powerful feature, opening up applications to systems where such expressions are intractable (e.g., those involving neural networks or optimization-based controllers).
  • Convexification and Relaxation: The transformation of the problem into a convex semi-infinite program and then to a finitely constrained problem is a clever way to make the problem computationally tractable.

Key Results

The paper presents two main theorems (Theorem 3.1 for Lyapunov stability and Theorem 3.2 for asymptotic stability) that formalize the algorithmic procedure. The effectiveness of the method is demonstrated through numerous numerical examples, including:

  • A nonlinear planar vector field.
  • The van der Pol oscillator.
  • A whirling pendulum.
  • A 5-d hyperchaotic system.
  • A power system model.
  • A non-smooth system.
  • A Rayleigh problem with control constraints.

In each case, the algorithm successfully identified a Lyapunov function, and the accompanying figures illustrate the satisfaction of the stability conditions. The paper also highlights the flexibility of choosing different dictionaries for the candidate Lyapunov functions.

Limitations and Future Work

  • Feasibility Dependence: The success of the algorithm hinges on the "feasibility" of the constructed convex semi-infinite programs, which in turn depends on the judicious selection of the "candidate Lyapunov triplet" (neighborhood, class K functions, and dictionaries). The paper acknowledges that the algorithm might not be able to detect infeasibility if the chosen triplet is not rich enough.
  • No Infeasibility Certificates: Unlike some other methods (like SOSTOOLS), this approach, relying on relaxed finite-constraint problems, may not provide certificates of infeasibility if a Lyapunov function of the chosen form does not exist.
  • Future Work: The authors suggest extensions to robust and stochastic stability, as well as the synthesis of control Lyapunov functions. They also mention that results along these directions will be reported subsequently.

Summary updated

BibTeX
@misc{gupta2023algorithmic,
  author = {Raavi Gupta and Sameep Chattopadhyay and Pradyumna Paruchuri and Debasish Chatterjee},
  title = {{On the Algorithmic Construction of Lyapunov Functions for Continuous Vector Fields}},
  year = {2023},
  doi = {10.2139/ssrn.4571500},
  howpublished = {SSRN},
}
Figure