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
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