Semidefinite Programming Relaxations and
Algebraic Optimization in Control

Pablo A. Parrilo (ETH Zürich) and Sanjay Lall (Stanford University)

Workshop presented at the 42nd IEEE Conference on Decision and Control, Maui HI, USA, December 8th, 2003

This course focuses on 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 will make 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.

All slides are in PDF format. Go to the Adobe website to download a viewer if you don't have one.

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

Guest lecturers:

  1. Lieven Vandenberghe (UCLA): Nonnegative polynomials, SDP formulations, and primal-dual interior point methods (pdf)
  2. Stephen Prajna (Caltech): Barrier Certificates for Nonlinear Model Validation (pdf)

See also the companion article:

Please feel free to send us your comments and suggestions.