Polyhedral Lyapunov Functions with Fixed Complexity

Polyhedral Lyapunov functions can approximate any norm arbitrarily well. Because of this, they are used to study the stability of Linear Time Varying and Linear Parameter Varying systems without being conservative. However, the computational cost of finding them grows unbounded as the size of their representation increases. We present an algorithm that attempts to find polyhedral functions while keeping the size of the representation fixed, allowing us to ne-tune the trade-off between conservativeness and computational complexity. The algorithm first measures the gap from contraction for a given polyhedral function. The solution is then used to find perturbations on the polyhedral function that reduce the contraction gap. The process is repeated until a valid polyhedral Lyapunov function is obtained. Because the algorithm is rooted in linear programming, additional linear constraints and objectives can be directly included. This leads to a flexible approach that can tackle both analysis and control synthesis problems.