Computation of local ISS Lyapunov functions for discrete-time systems via linear programming

This paper presents a numerical algorithm for computing ISS Lyapunov functions for discrete-time systems which are input-to-state stable (ISS) on compact subsets of the state space. The algorithm relies on solving a linear optimisation problem and delivers a continuous and piecewise affine ISS Lyapunov function on a suitable triangulation covering the given compact set excluding a small neighbourhood of the origin. The objective of the linear optimisation problem is to minimise the ISS gain. It is shown that for every ISS system there exists a suitable triangulation such that the proposed algorithm terminates successfully.