Short Course: Quantitative Local Analysis of Nonlinear Systems Using Sum-of-Squares Decompositions

Prepared and taught by A. Packard (UC Berkeley), G. Balas (U of Minnesota), P. Seiler (U of Minnesota), and U. Topcu.

Slides and Individual Workshop Web Sites

• Latest version of the notes (pdf).

• Short course at NASA Langley Research Center (Sept 30 and Oct 1, 2009)
  Workshop web site gives access to the slides, demo files, and the corresponding code.

• Pre-conference workshop at the American Control Conference 2009 (June 9, 2009)
  Workshop web site.

MATLAB Software

• SeDuMi is maintained by Lehigh University. See their website for downloads, installation instructions, etc. Notes on SeDuMi installation.

• You can download all the nonlinear analysis software (except SeDuMi) in one package. You can also download the individual packages

  • Script file to configure the MATLAB path for these packages (sosaddpath.m)

  • Multipoly: Package used to represent multivariate polynomials.

  • SOSOPT: General SOS optimization utility.

  • Nonlinear analysis code: The rest of the routines discussed in the workshop.

  • Polysys: Package used to model, simulate, and analyze nonlinear systems with polynomial dynamics.

  • Worstcase: Package to compute the induced gain of nonlinear systems using an iterative algorithm.

  • Worst-case simulation code.

• Demo files
  

Abstract

The focus of this workshop is computational tools to derive quantitative bounds on the behavior of uncertain, nonlinear dynamical systems. The target audience includes graduate students and researchers interested in computational methods for provable, quantitative assessment of nonlinear system behavior, including flight control, adaptive systems and system biology.

Three canonical analysis questions regarding behavior are considered: region-of-attraction, gain, and reachable set analysis. The uncertain dynamics are modeled in several ways, including polytopes of vector fields, parametric uncertainty, and unmodeled dynamics. Using elementary relaxation (e.g. S-procedure) techniques, the analysis problems are reformulated as bilinear (non-convex) sum-of-squares optimizations. The bilinearity arises due to product terms involving the Lyapunov (storage) function coefficients and the S-procedure multiplier coefficients. Rather than simply employ off-the-shelf bilinear solvers, we show that system-theoretic interpretations of the problem allow for some reduction in the complexity of the bilinear optimization. Specifically, we use simulations to derive convex outer-bounds on the set of feasible storage functions. Drawing samples from this outer-bound set appears to be a very effective approach to initialize various algorithms to the bilinear problem.

Robustness theorems are developed for parametric uncertainty, using a simplistic, but parallelizable methodology. Unmodeled dynamics are also considered, employing a local small-gain theorem.

The workshop will present many examples, from simply visualized 2-state “textbook” problems to 10-state (or higher) physically-motivated problems. All examples will be solved using open-source software (in the form of Matlab m-files) provided to the participants (and accessible at sourceforge.net) along with Matlab and additional open-source software (such as SeDuMi, SOSTools). All participants are encouraged to bring laptops and actively participate in the interactive computational section (late afternoon) of the workshop. All presented examples will be distributed.

The workshop will address the limitation of the tools and the approach, which mostly arises from dimensionality of the state, leading to very large (nonconvex) bilinear semidefinite programs.

An outline of the workshop’s topics is as follows:

• Overview of problems considered, and other problems that can be addressed similarly, literature review of related techniques;

• Prelimiaries: S-procedure and extensions for set containment certificates, SOS decompositions;

• Problem formulations - the approach for each analysis problem follows six steps:

  • Lyapunov/storage function formulation;

  • S-procedure and SOS relaxation to a bilinear semidefinite program;

  • mathematical connection to related linearized analysis;

  • assessing the certification power of a given storage function;

  • SDP/SOS iteration to improve a given storage function’s certification power;

  • incorporating simulation to pick promising storage functions.

• Handling uncertain dynamics: polytopes of vector fields; parametric uncertainty, unmodeled dynamics;

• Strategies for solving large-scale problems;

• Interactive computational exercises.
  

The goal of the work (sponsored by AFOSR and NASA) is to develop computationally plausible schemes for analyzing the behavior of systems with (for example) 15-20 states, unmodeled dynamics, handful (e.g. 3) uncertain parameters, and cubic vector fields. Several examples, heading towards those goals, will be presented.

Extensions

• CDS 270 - Verification in Controls: Graduate level course at Caltech co-taught by U. Topcu in Fall 2009.

• Shorter version of the short course slides for the V&V MURI hands-on workshop at Caltech (Sept 17, 2009).