Abstract. In this paper, we present a method for computing a basin of attraction to a target region for polynomial ordinary differential equations. This basin of attraction is ensured by a Lyapunov-like polynomial function that we compute using an interval based branch-and-relax algorithm. This algorithm relaxes the necessary conditions on the coefficients of the Lyapunov-like function to a system of linear interval inequalities that can then be solved exactly. It iteratively refines these relaxations in order to ensure that, whenever a non-degenerate solution exists, it will eventually be found by the algorithm. Application of an implementation to a range of benchmark problems shows the usefulness of the approach. Key words. basin of attraction, stability, constraint solving, interval computation, algorithms AMS subject classifications. 65G40, 68U99, 65P40 1. Introduction. A sufficient condition for verifying stability of ordinary differential equations is the existence of a Lyapunov function [16] . In cases where the differential equation is polynomial, due to decidability of the theory of real-closed fields [44] , there is an algorithm that, for a given polynomial with parametric coefficients, decides whether there are instantiations of these parameters resulting in a Lyapunov function. However, all the existing decision procedures (e.g., implemented in the software packages QEPCAD [4] or REDLOG [11]), while being able to solve impressively difficult examples, are not efficient enough to be able to solve this problem in practice. Recently, a method based on sum of squares decomposition [26, 27] has appeared that can compute Lyapunov functions for some realistic examples. However, being based on the classical stability, it does not allow reasoning about target regions (and hence it requires an equilibrium), and only results in Lyapunov functions that characterize the behavior of the given system locally (around the equilibrium) or globally (on the whole state space). Another option is to try to compute a Lyapunov function of a linearization of the non-linear problem around a given equilibrium point, and compute a basin of attraction for this Lyapunov function with respect to the original, non-linear problem [13, 10] . However, due to the information loss introduced by the linearization process, this basin of attraction will usually be very small. In this paper we will provide an algorithm for computing a Lyapunov-like function for the original, non-linear problem, which will provide us with a basin of attraction to a given target region. This target region can, for example, be the smaller basin of attraction obtained by linearization, hence ensuring attraction to the equilibrium. This algorithm is also fit to deal with systems with small interval uncertaintiesa corresponding extension of the algorithms with the necessary interval arithmetic
The RSOLVER by Ratschan and She REF computes Lyapunov-like functions for continuous system.
Providing a Basin of Attraction to a Target Region of Polynomial Systems by Computation of Lyapunov-Like Functions
SIAM J. Control and Optimization
SIAM J. Control and Optimization
Mathematics Computer Science