Course on LMI optimization with applications in control
(Didier Henrion, LAAS-CNRS, Toulouse, France and FEL-CVUT, Prague, Czech Republic)

Czech Technical University, Prague, Czech Republic - March 2011

Venue and dates

The course is given at the Charles Square campus of the Czech Technical University, in the historical center of Prague (Karlovo Namesti 13, 12135 Praha 2) during the first two weeks of March 2011. It consists of six two-hour lectures, given on Tuesday 1 March, Thursday 3 March and Tuesday 8 March, from 10am to noon, and from 2pm to 4pm.

Description

This is a course for graduate students or researchers with a background in linear control systems, linear algebra and convex optimization.

The focus is on semidefinite programming (SDP), or optimization over linear matrix inequalities (LMIs), an extension of linear programming to the cone of positive semidefinite matrices. Since the 1990s, LMI methods have found numerous applications mostly in combinatorial optimization, systems control and signal processing.

Outline

The course starts with fundamental mathematical features of linear matrix inequalities:
  • Part 0: general introduction, course outline and material
  • Part 1: technical background on linear algebra, numerical methods, cones, duality and convexity
  • Part 2: what is an LMI ? history, connection with semidefinite programming (SDP)
  • Part 3: LMI duality, alternatives, Farkas lemma, S-procedure

    More recent material covers the applications of LMIs in polynomial optimization:

  • Part 4: convex LMI modelling, classification of convex semialgebraic sets that can be represented with LMIs, lift and project techniques
  • Part 5: nonconvex LMI modelling, BMI, Shor's relaxation, polynomial moments and sum-of-squares, Lasserre's hierarchy of LMI relaxations for non-convex polynomial optimization

    We also briefly survey recent developments in semidefinite solvers and software packages:

  • Part 6: LMI solvers, basics of interior-point algorithms, latest achievements in software and solvers for LMIs and BMIs

    The end of the course focuses on the use of measures for static polynomial optimisation problems and occupation measures for differential equations and related optimal control problems:

  • Part 7<: Measures, occupation measures and control problems

    This last part surveys most of the material covered in Parts 5, but through the lense of measure theory and the related generalized problem of moments. Moreover, it extends these ideas to differential equations and optimal control framework, and it describes several research directions along these lines.

    Homeworks and exam

    Homeworks are handed out during the course. A written examination can be organized.

    Last updated on 24 February 2011.