PIMS Voyageur Colloquium: Henry Wolkowicz
Topic
Sensor Network Localization
Speakers
Details
Taking advantage of Degeneracy in Cone Optimization; Applications to Euclidean Distance Completion Problems including: Sensor Network Localization and Molecular Conformation.
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.
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.
