Semidefinite Programming and Algebraic Optimization in Control

  • Pablo Parrilo and Sanjay Lall
  • 17th International Symposium on Mathematical Theory of Networks and Systems
  • Kyoto International Conference Hall, Kyoto, Japan, July 24-28, 2006

Slides

  • 1. Introduction (ps, pdf, 2up)
  • 2. Convexity and Duality (ps, pdf, 2up)
  • 3. Quadratically Constrained Quadratic Programming (ps, pdf, 2up)
  • 4. Algebra and Duality (ps, pdf, 2up)
  • 5. Linear Inequalities and Elimination (ps, pdf, 2up)
  • 6. Computational Complexity (ps, pdf, 2up)
  • 7. The Algebraic Geometric Dictionary (ps, pdf, 2up)
  • 8. Sum of Squares (ps, pdf, 2up)
  • 9. Interpretations, Liftings, SOS and Moments (ps, pdf, 2up)
  • 10. Positivstellensatz (ps, pdf, 2up)
  • 11. Semialgebraic Lifting (ps, pdf, 2up)
  • 12. Further Applications (ps, pdf, 2up)
  • 13. Summary (ps, pdf, 2up)

Workshop Outline

This workshop covers recent developments in computational methods using semidefinite programming for optimization problems involving polynomial equations and inequalities.

There has been much recent progress in this area, combining theoretical developments in real algebraic geometry with semidefinite programming to develop effective computational approaches to these problems.

The course makes particular emphasis on general duality properties as providing suboptimality or infeasibility certificates, and focus on the exciting developments that have occurred in the last few years, including relaxations of combinatorial optimization problems, and algebraic methods such as sum-of-squares.

The course is punctuated by many application examples, including:

  • Numerical solution of Hamilton-Jacobi equations for hybrid/switching systems, e.g. computing reachable sets and controllability.
  • Finding non-quadratic Lyapunov functions for nonlinear dynamical systems.
  • Stabilizing controllers for nonlinear systems.
  • Quadratic programming, e.g. robustness analysis, strengthening the S-procedure, computation of the structured singular value.
  • Certification of entanglement for analysis of quantum devices.
  • Graph problems: max-cut, independent set, cliques.