Vorträge im Schwerpunkt Reelle Geometrie und Algebra
Donnerstag, 18. November 2010, um 17:00 Uhr
in F426
(Schwerpunktskolloquium, Scheiderer)
Dr. Hartwig Bosse
(Frankfurt)
Faces of spectrahedra in
the max-cut SDP hierarchy
Abstract:
The aim of the talk is on one hand to present possible mechanisms, that
can be used to sharpen symmetric SDP-relaxations of 0-1-optimization
problems. On the other hand, the talk presents insights on the
geometric structure of a special set of spectrahedra.
We revisit a
result of Monique Laurent on semidefinite relaxation hierarchies for
max cut: The positive-semidefinite matrices X>0
with Xii=1 form the ground
set for a semi-definite programming
relaxation of the max-cut problem. By adding new columns and rows to
the original matrix X,
the resulting set can be sharpened into the
cut polytope, i.e., the convex hull of all cut-matrices. This process
essentially results in a Lasserre hierarchy of SDPs for max cut.
Using reverse symmetry reduction on a trivial LMI-representaion of the
cut polytope, we show that the spectrahedra corresponding to the
intermediate SDPs all inherit a subset of faces from the cut-polytope.
To this end we interpret the cut-polytope as the convex hull of
characters of Z2⊗n. We then prove that for
cyclic
groups such "character polytopes'' have a nice hierarchy of
approximating spectrahedra.
Es wird Gelegenheit gegeben, sich vorher (ab 16.30 Uhr) im Commoncenter
F 441 bei Tee und Kaffee zu treffen.
zuletzt
geändert am 12. November 2010
