Henry Wolkowicz; Taking Advantage of Degeneracy in Cone Optimization: with Applications to Sensor Network Localization

November 13, 2014, 4:00pm
EEB 003
Henry Wolkowicz, Depart­ment of Math­e­mat­ics, Uni­ver­sity of Water­loo.
Taking Advantage of Degeneracy in Cone Optimization: with Applications to Sensor Network Localization

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.

Leave a Reply

Your email address will not be published. Required fields are marked *