A Tutorial on Semidefinite Programming and Applications

abstract:

Semidefinite Programming, SDP, refers to optimization problems where the vector variable is a symmetric matrix which is required to be positive semidefinite. Though SDPs (under various names) have been studied as far back as the 1940s, the interest has grown tremendously during the last ten years. This is partly due to the many diverse applications in e.g. engineering, combinatorial optimization, and statistics. Part of the interest is due to the great advances in efficient solutions for these types of problems.

This lecture is an introduction to the theory, algorithms, and applications for semidefinite programming.

Motivation and Basic Properties
Duality and Optimality Conditions (Comparisons with Linear Programming)
Examples/Applications
- Differential Equations
- Combinatorial Optimization
  - Problems: Max-Cut; Quadratic Assignment; Graph Partitioning
- Nonlinear Programming
Interior-Point Algorithms (State of the Art, Sparsity Issues, Open Problems)
Empirical Evidence