Title: Understanding and improving convex formulations via lifted representations
| Speaker: | Hamza Fawzi |
| Affiliation: | MIT |
| Room: | MC 5417 |
Abstract:
Mathematical
optimization
problems
arise
in
all
areas
of
science
and
engineering.
The
distinction
convex/nonconvex
has
usually
played
the
role
of
boundary
between
"easy"
and
"hard"
problems.
In
the
recent
years
it
was
shown
that
several
hard
nonconvex
problems
can
be
very
successfully
tackled
using
so-called
convex
relaxations.
Such
techniques
have
been
applied
in
diverse
areas
such
as
signal
processing,
imaging,
statistics,
control
theory,
robotics,
power
flow,
etc.
At
the
heart
of
convex
relaxation
methods
lies
the
question
of
obtaining
tractable
representations
of
a
convex
hull
of
a
set
of
points.
In
this
talk
I
will
discuss
lifted
representations
of
convex
sets,
in
which
the
"hard"
convex
set
is
expressed
as
the
projection
of
a
simpler
one
living
in
a
higher-dimensional
space.
I
will
present
a
new
method
to
construct
improved
semidefinite
programming
lifts
for
polytopes
and
will
give
two
applications
of
our
method.
First
I
will
show
how
it
provides
the
first
family
of
polytopes
in
increasing
dimensions
with
a
growing
gap
between
LP
and
SDP
extension
complexity.
Second
I
will
show
how
our
method
can
be
used
to
solve
a
conjecture
of
Laurent
from
2003
on
the
Lasserre
hierarchy
for
the
maximum
cut
problem.