Facial Reduction for Cone Optimization

Henry Wolkowicz (University of Waterloo)

The Slater constraint qualification (SCQ) is essential for many classes of convex programs, e.g., Linear Programming (LP), ordinary convex programming (CP), and cone optimization (CO). However, SCQ fails for many problems, e.g., for for many instances of semidefinite programming (SDP) that arise from relaxations of computationally hard problems. This degeneracy results in theoretical problems (possible loss of strong duality) as well as numerical problems (due to ill-posedness). A theoretical tool to regularize these problems uses facial reduction. We present a backwards stable approach for preprocessing a general SDP using facial reduction. In addition, we consider several specific applications where the structure of the problem surprisingly allows us to exploit the degeneracy.
Rather than presenting numerical difficulties, we obtain smaller stable problems that allow for efficient high accuracy solutions for many large scale instances. In particular, we look at facial reduction for sensor network localization (SNL) and molecular conformation (MC). For SNL we are able to exploit the low rank of the optimal solution and solve huge problems; equivalent to an SDP with order $10^9$ variables and $10^6$ constraints, to $16$ decimal accuracy in a few minutes on a laptop. For MC, one can exploit the amino acid structure in protein molecules to significantly reduce the size of problems before using an SDP solver.

Work with: Cheung/Drusvyatskiy/Krislock