Semidefinite Programming Relaxations and
Algebraic Optimization in Control
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
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.
- Introduction (pdf)
- Convexity and Duality (pdf)
- Quadratically Constrained Quadratic Programming (pdf)
- Algebra and Duality (pdf)
- Linear Inequalities and Elimination (pdf)
- Computational Complexity (pdf)
- The Algebraic-Geometric Dictionary (pdf)
- Sum of Squares (pdf)
- Interpretations, Liftings, SOS, and Moments (pdf)
- The Positivstellensatz (pdf)
- Semialgebraic Lifting (pdf)
- Further Applications (pdf)
- Summary (pdf)
- Lieven Vandenberghe (UCLA):
Nonnegative polynomials, SDP formulations, and primal-dual interior point methods
- Stephen Prajna (Caltech):
Barrier Certificates for Nonlinear Model Validation (pdf)
See also the companion article:
Semidefinite programming relaxations and algebraic optimization in Control
P. A. Parrilo, S. Lall,
European Journal of Control, Vol. 9, No. 2-3, 2003.
Please feel free to send us your comments and suggestions.