Strong Duality in Semidefinite Programming and Facial Reduction with Applications to Sensor Network Localization and Molecular Conformation
| Speaker: | Henry Wolkowicz |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics & Computer Building (MC) 5158 |
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
109 variables
and
106 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.