Linear Relaxations of Polynomial Positivity for Polynomial Lyapunov Function Synthesis

Document Type

Article

Publication Date

9-2016

Publication Source

IMA Journal of Mathematical Control and Information

Abstract

We examine linear programming (LP) based relaxations for synthesizing polynomial Lyapunov functions to prove the stability of polynomial ordinary differential equations (ODEs). Our approach starts from a desired parametric polynomial form of the polynomial Lyapunov function. Subsequently, we encode the positive definiteness of the function, and the negation of its derivative, over the domain of interest. We first compare two classes of relaxations for encoding polynomial positivity: relaxations by sum-of-squares (SOS) programmes, against relaxations based on Handelman representations and Bernstein polynomials, that produce linear programmes. Next, we present a series of increasingly powerful LP relaxations based on expressing the given polynomial in its Bernstein form, as a linear combination of Bernstein polynomials. Subsequently, we show how these LP relaxations can be used to search for Lyapunov functions for polynomial ODEs by formulating LP instances. We compare our techniques with approaches based on SOS on a suite of automatically synthesized benchmarks.

Inclusive pages

723–756

ISBN/ISSN

0265-0754

Comments

Permission documentation on file.

Publisher

Oxford University Press

Volume

33

Peer Reviewed

yes

Issue

3

Link to Full Text

Share

COinS