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

Abstract

The Slater constraint qualification fails 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 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 solve huge problems equivalent to an SDP with order TeX Embedding failed! variables and TeX Embedding failed! constraints to 16 decimal accuracy in a few minutes on a laptop. For MC, we are able to exploit the amino acid structure in protein molecules to significantly reduce the size of problems before using an SDP solver.

Details