Henry Wolkowicz, University of Waterloo
ABSTRACT:
The elegant theoretical results for strong duality and strict
complementarity for linear programming, LP, lie behind the success of
current algorithms. However, the theory and preprocessing techniques
that are successful for LP can fail for cone programming over
nonpolyhedral cones.
Surprisingly, many important applications of
semidefinite programming, SDP,
that arise from relaxations of hard combinatorial problems are
degenerate. (Slater's constraint qualification fails.)
This includes relaxations for problems such as the: Quadratic Assignment; Graph
Partitioning; Set Covering and partitioning; and sensor network localization
and molecular conformation. Rather than being
a disadvantage, we show that this degeneracy can be exploited. In
particular, several huge instances of SDP completion problems can be
solved quickly and to extremely high accuracy. In particular, we
illustrate this on the sensor network localization problem.