Linear relaxations of polynomial positivity for polynomial Lyapunov function synthesis

DOI10.1093/IMAMCI/DNV003zbMATH Open1397.93189arXiv1407.2952OpenAlexW1978884939MaRDI QIDQ4683987FDOQ4683987

Authors: Mohamed Amin Ben Sassi, Sriram Sankaranarayanan, Xin Chen, Erika Ábrahám 

Publication date: 27 September 2018

Published in: IMA Journal of Mathematical Control and Information (Search for Journal in Brave)

Abstract: In this paper, we examine linear programming (LP) based relaxations for synthesizing polynomial Lyapunov functions to prove the stability of polynomial ODEs. A common approach to Lyapunov function synthesis starts from a desired parametric polynomial form of the polynomial Lyapunov function. Subsequently, we encode the positive-definiteness of the function, and the negative-definiteness of its derivative over the domain of interest. Therefore, the key primitives for this encoding include: (a) proving that a given polynomial is positive definite over a domain of interest, and (b) encoding the positive definiteness of a given parametric polynomial, as a constraint on the unknown parameters. We first examine two classes of relaxations for proving polynomial positivity: relaxations by sum-of-squares (SOS) programs, against relaxations that produce linear programs. We compare both types of relaxations by examining the class of polynomials that can be shown to be positive in each case. Next, we present a progression of increasingly more powerful LP relaxations based on expressing the given polynomial in its Bernstein form, as a linear combination of Bernstein polynomials. The well-known bounds on Bernstein polynomials over the unit box help us formulate increasingly precise LP relaxations that help us establish the positive definiteness of a polynomial over a bounded domain. 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 approaches to synthesizing Lyapunov functions with approaches based on SOS programming relaxations.

Full work available at URL: https://arxiv.org/abs/1407.2952

Recommendations

• Stability and stabilization of polynomial dynamical systems using Bernstein polynomials
• A linear programming relaxation based approach for generating barrier certificates of hybrid systems
• Reachability analysis of polynomial systems using linear programming relaxations
• Automatically discovering relaxed Lyapunov functions for polynomial dynamical systems
• Lyapunov function construction for ordinary differential equations with linear programming

zbMATH Keywords

Bernstein polynomialsstabilityLyapunov functionsinterval arithmeticsum-of-squarespositive polynomialsHandelman representations

Mathematics Subject Classification ID

Linear programming (90C05) Synthesis problems (93B50) Control/observation systems governed by ordinary differential equations (93C15) Lyapunov and storage functions (93D30)

Cited In (7)

• Automatically discovering relaxed Lyapunov functions for polynomial dynamical systems
• Convergent Relaxations of Polynomial Matrix Inequalities and Static Output Feedback
• Template polyhedra and bilinear optimization
• Phase portraits, Lyapunov functions, and projective geometry. Lessons learned from a differential equations class and its aftermath
• Validating numerical semidefinite programming solvers for polynomial invariants
• FOSSIL
• Semidefinite Approximations of Reachable Sets for Discrete-time Polynomial Systems

This page was built for publication: Linear relaxations of polynomial positivity for polynomial Lyapunov function synthesis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4683987)