STOR Coloquium: Henry Wolkowicz (University of Waterloo)

Taking advantage of Degeneracy in Cone Optimization with Applications to 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, 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 and Molecular conformation problems.

Refreshments will be served at 3:30pm in the 3rd floor lobby of Hanes Hall