Construction of Polynomial Lyapunov Functions Using Genetic Programming and Sparse Optimization

We propose a hybrid evolutionary-sparse optimization framework for the automated synthesis of polynomial Lyapunov functions certifying exponential stability of nonlinear autonomous systems on a prescribed compact domain. Candidate Lyapunov functions are encoded as height-bounded genetic programming (GP) expression trees restricted to addition and multiplication, which guarantees polynomial semantics and yields interpretable closed-form certificates. Each tree is expanded into a canonical polynomial representation and mapped to its induced monomial support. Conditioning on this support, we fit the coefficients using a constrained sparse-optimization routine that minimizes an empirical Lyapunov penalty together with a sparsity-promoting term, implemented through a staged proximal scheme based on firm thresholding. The coefficient-fitting step is exposed as a feasibility oracle that returns "feasible" precisely when the sampled quadratic bounds and dissipation inequality hold on the chosen sample set. We establish two complementary guarantees. First, under full-support regrow mutation, we derive an explicit finite-generation (hitting-time) bound for the GP outer loop: if at least one oraclefeasible template exists in the height-bounded search class, then, for any target confidence level, there exists a finite number of generations after which a feasible structure is found with at least that confidence; moreover, the non-discovery probability decreases geometrically in the number of generations, with rate governed by the offspring count, mutation probability, minimal regrow mass, and the number of feasible templates. Second, we provide deterministic sampling certificates on a compact set, showing that sufficiently small empirical violation implies satisfaction of the Lyapunov inequalities on the full domain. Numerical experiments on benchmark systems demonstrate that the method produces sparse, human-readable Lyapunov polynomials.