Taking advantage of Degeneracy in Cone Optimization

Henry Wolkowicz
University of Waterloo
Combinatorics and Optimization

The elegant theoretical results for strong duality and strict complementarity for linear programming, LP, lie behind the success of current algorithms. In addition, preprocessing is an essential step for efficiency in both simplex type and interior-point methods. However, the theory and preprocessing techniques can fail for cone programming over nonpolyhedral cones.

We take a fresh look at known and new results for duality, optimality, constraint qualifications, CQ, and strict complementarity, for linear cone optimization problems in finite dimensions. One theme is the notion of minimal representation of the cone and the constraints. This provides a framework for preprocessing cone optimization problems in order to avoid both the theoretical and numerical difficulties that arise due to the (near) loss of the strong CQ, strict feasibility.

Surprisingly, many instances of semidefinite programming, SDP, problems that arise from relaxations of hard combinatorial problems are degenerate (CQ 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 problem.

Presentation (PDF File)

Back to Workshop II: Numerical Methods for Continuous Optimization