Title: A gentle overview of SDP representable sets and SDP applications
| Speaker: | Mehdi Karimi |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract:
Semidefinite
Programming
(SDP)
has
been
extensively
studied
in
the
last
two
decades
due
to
its
widespread
applications
in
operations
research
and
combinatorial
optimization.
Currently,
there
are
many
efficient
codes
for
solving
SDP
problems.
This
is
an
introductory
talk
that
starts
with
the
definition
of
SDP
representability
and
continues
with
some
examples
of
SDP
representable
sets.
We
show
how
to
write
an
SDP
relaxation
for
a
combinatorial
optimization
problem
and
at
the
end
we
go
over
the
idea
of
Goemans-Williamson
approximation
algorithm
for
the
MAXCUT
problem."
The
presentation
will
be
based
on
the
following
manuscripts
https://web.stanford.edu/~boyd/papers/pdf/semidef_prog.pdf
http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf
For
more
information
about
our
reading
group,
please
visit
our
webpage
http://www.math.uwaterloo.ca/~deolivei/reading.htm