Tutte seminar - Henry Wolkowicz

Strong Duality in Semidefinite Programming and Facial Reduction with Applications to Sensor Network Localization and Molecular Conformation

Abstract:

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 many instances of semidefinite programming (SDP) that arise from relaxations of computationally hard problems. Thisdegeneracy 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 an SDP using facial reduction. 

In addition, we consider several applications where the structure of the problem 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⁹ variables and 10⁶ 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.