Semidefinite programming

Abstrakt:

Semidefinite programming has attracted interest in the computational complexity community as a tool for providing lower bounds on optimal values of certain combinatorial optimization problems. It has also become an important tool for solving many design problems in control and communications theory.

The aim of this talk is to give an introduction to semidefinite programming. We start with a discussion on linear programming and duality. These results are then generalized to semidefinite programming, with discussion on important differences. The ability to solve semidefinite programs efficiently has been enhanced quite significantly by the development of interior methods. We give a basic description of interior methods. Finally, a few application examples are discussed.