A Linear Program to Compare Path-Complete Lyapunov Functions

We provide an algorithmic procedure allowing to compare stability certificates for discrete-time switching systems and in specific Path-Complete Lyapunov functions (PCLFs). These mathematical objects consist of a set of positive definite functions and a set of Lyapunov inequalities, encoded in a directed, labeled graph. Given two such graphs, we formulate necessary and sufficient conditions to decide if the existence of a PCLF for the first graph implies existence of a PCLF for the second graph, where the corresponding set of functions is constructed by conic combinations of the set of functions related to the first PCLF. The conditions depend only on the topologies of the two graphs and can be verified by solving a linear program. It is the first systematic approach to compare the conservativeness of PCLFs.