Monday, November 10, 2014
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
Polytopes can be given as the convex hull of a finite point set
(V-polytope) or as the intersection of finitely many halfspaces
(H-polytope). Given an H-polytope $P$ and a V-polytope $Q$,
the decision problem whether $P$ is contained in $Q$ is
co-NP-complete ("Polytope Containment Problem").
This hardness remains if $P$ is restricted to be a standard cube
and $Q$ is restricted to be the affine image of a cross polytope.
While this hardness classification by Freund and Orlin dates
back to 1985, there seems to be only limited progress on that
problem so far.
In the talk, we approach the Polytope Containment from the
viewpoint of a bilinear feasibility problem and in connection
with linear and semidefinite relaxations. We will explain
the connections to Handelman's and Putinar's Positivstellensatz
and thus obtain hierarchies of linear programs
and semidefinite programs, respectively, to decide the containment
problem. We study their geometric properties and Positivstellensatz
certificates.
As a main result, we show that under mild and explicitly known
preconditions the semidefinite hierarchy converges in finitely
many steps. In particular, this is the case if $P$ is the standard
cube and $Q$ is the standard cross polytope.
Joint work with Kai Kellner.
Colloquium - 16:00
Abstract:
The Theta rank of a finite point configuration V is the maximal degree
necessary for a sum-of-squares representation of a non-negative linear
function on V. This is an important invariant for polynomial optimization
that is in general hard to determine.
The levelness is a geometric property of a configuration that provides an
upper bound to the Theta rank. Furthermore, it has been shown that
configurations with (minimal) Theta rank =1 are exactly the 2-level
configurations.
I will consider the class of 0/1-point configurations arising from
matroids and characterize the ones with minimal Theta rank by means of
combinatorial properties directly linked to levelness. I will also present
interesting features of this matroid family together with some enumerative
aspects.
For the case of graphic matroids I will present more general results about
levelness and a partial characterization of graphs whose configuration is
of Theta rank=2.
The talk is based on works with R. Sanyal and with J. Rue.