LP Infeasibility – The Pursuit of Intelligent Discretization

Speaker: Tobias Leth
Affiliation: Aalborg University

Abstract:  The problem of finding Lyapunov functions to certify the stability of dynamical systems is of great interest to engineers worldwide. When considering polynomial systems, the task of finding a polynomial Lyapunov function can be cast as a synthesis problem. One way to do this is by describing the vector field and the Lyapunov function in the Bernstein basis, as opposed to the monomial basis.

In the Bernstein basis the classical Lyapunov criteria of positive/negative definiteness can be translated into conditions on the coefficients of the Lyapunov functions and its Lie derivative. Seeing as the coefficients of the Lie derivative are linear in the coefficients of the Lyapunov function, the synthesis problem becomes a linear programming problem.  Polynomials in the Bernstein basis are defined on simplices. The size of the linear program depends on the number of simplices used to triangulate the domain. In order to keep the problem size at a minimum, one will initially triangulate using a minimum of simplices. However, this opens for the possibility of arriving at a linear program with no solution. This is overcome by sub-dividing the simplices into smaller and smaller simplices until the resulting linear problem becomes solvable.

Using this iterative approach does not necessarily require the sub-division of all simplices before the resulting linear problem becomes solvable. By utilizing information from the previous infeasible linear problem one can create a customized triangulation for setting up the next linear program.

Since many scholars are unfamiliar with the Bernstein basis, I introduce it in some detail. I show how the Lyapunov criteria are translated to polynomials in the Bernstein basis, and how this allows for an algorithmic approach for the synthesis of Lyapunov functions. When faced with infeasibility, using Farkas’ lemma I show how to obtain a non-trivial triangulation.

Biography: Tobias Leth received his B.Sc (2012) and M.Sc (2014) with specialisation in Mechatronic Control Engineering from the Department of Energy Technology at Aalborg University. He is now a PhD student at the Department of Electronic Systems in the Automation and Control Section. He is currently visiting Colorado to study for five month with Professor Sriram Sankaranarayanan from University of Colorado at Boulder. His research interests include automated control design and robotics.   Before engaging in education Tobias Leth served as a Sergeant in the Danish Army.

For more information, contact Prof. Lieven Vandenberghe (vandenbe@ee.ucla.edu)

Date/Time:
Date(s) - Dec 01, 2016
3:00 pm - 4:30 pm

Location:
E-IV Tesla Room #53-125
420 Westwood Plaza - 5th Flr., Los Angeles CA 90095