Tutorial on
Semidefinite Programming and its Application to Solving/Approximating
Hard Combinatorial Optimization Problems
Prof. Henry Wolkowicz
Univiversity of Waterloo
Department of Combinatorics and Optimization
Waterloo, Ont. CANADA
URL http://orion.math.uwaterloo.ca/~hwolkowi
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
twenty 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 is a tutorial on the theory, algorithms, and
applications for SDP. We emphasize the
applications to solving hard combinatorial optimization problems, e.g.
to: Max-Cut; Quadratic Assignment; Graph Partitioning; and
Ad-hoc Sensor Localization.