Feasibility problems: from alternating projections to matrix completions.
| Speaker: | Dmitriy Drusvyatskiy |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 5158 |
Abstract:
Feasibility
problems
permeate
computational
mathematics.
In
the
most
general
framework,
we
may
seek
a
point
in
the
intersection
of
two
arbitrary
closed
sets.
I
will
revisit
an
intuitive
and
widely
used
algorithm
for
such
problems
due
to
Van
Neumann
–
the
method
of
alternating
projections.
The
algorithm
proceeds
by
projecting
an
iterate
onto
one
set,
then
onto
the
next,
and
so
on.
For
two
sets
intersecting
rigidly
(in
the
sense
that
small
perturbations
do
not
destroy
the
intersection),
the
method
converges
linearly.
Reassuringly,
for
semi-algebraic
intersections
---
prototypical
pathology
free
problems
in
optimization
---
``generic’’
intersections
are
indeed
rigid.
On
the
other
hand,
for
highly
structured
feasibility
problems
(such
as
those
coming
from
graph
embeddings),
the
two
relevant
sets
tend
to
intersect
only
``tangentially’’.
I
will
illustrate,
by
focusing
on
the
semi-definite
and
Euclidean
distance
completion
problems,
how
this
seemingly
complicating
feature
can
instead
be
used
as
an
advantage.
Joint
work
with
V.
Cheung
(Waterloo),
A.D.
Ioffe
(Technion),
N.
Krislock
(NIU),
A.S.
Lewis
(Cornell),
G.
Pataki
(UNC),
H.
Wolkowicz
(Waterloo).