Title: Taking advantage of Degeneracy in Cone Optimization;
Applications to Euclidean Distance Completion Problems including:
Sensor Network Localization and Molecular Conformation.
Math and Stats at York University
, Friday, April 27, 2012, ?PM.
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 instances of semidefinite programming, SDP, problems that
arise from relaxations of hard combinatorial problems are degenerate.
(Slater's constraint qualification fails.) Rather than being a disadvantage,
we show that this degeneracy can be exploited.
In particular, we look at low rank Euclidean Distance matrix completion
problems. We show that these problems can be solved
quickly and to extremely high accuracy.
In particular, we illustrate this on
sensor network localization and Molecular conformation problems.
slides (pdf file)