Linear relaxations of polynomial positivity for polynomial Lyapunov function synthesis

DOI10.1093/IMAMCI/DNV003MaRDI QIDQ4683987zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cited in

(9)

• Phase portraits, Lyapunov functions, and projective geometry. Lessons learned from a differential equations class and its aftermath
• Semidefinite Approximations of Reachable Sets for Discrete-time Polynomial Systems
• A linear programming relaxation based approach for generating barrier certificates of hybrid systems
• Automated and sound synthesis of Lyapunov functions with SMT solvers
• Validating numerical semidefinite programming solvers for polynomial invariants
• Template polyhedra and bilinear optimization
• Convergent Relaxations of Polynomial Matrix Inequalities and Static Output Feedback
• FOSSIL
• Automatically discovering relaxed Lyapunov functions for polynomial dynamical 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)