3rd SDP days
Lectures by young researchers
Titles and abstracts
Geometry of the Copositive and Completely Positive Cones (Peter Dickinson, University of Groningen)
The copositive cone, and its dual the completely positive cone, have useful applications in optimisation, however the membership problems for these cones are NP-hard. In this talk we analyse some of the geometry of these cones. We discuss a way of representing all the maximal faces of the copositive cone along with a simple equation for the dimension of each one. In doing this we show that the copositive cone has faces which are isomorphic to positive semidefinite cones. We also look at some maximal faces of the completely positive cone and find their dimensions. Additionally we consider extreme rays of the copositive and completely positive cones and show that every extreme ray of the completely positive cone is also an exposed ray, but the copositive cone has extreme rays which are not exposed rays.
Copositive formulation for the stability number of infinite graph (Cristian Dobre, University of Groningen)
We show that the stability number (independence number) of an infinite graph is the optimal solution of some infinite dimensional
copositive program. For this a duality theory between the primal convex cone of copositive kernels and the dual convex cone of completely positive measures is developed. We compare this new theory with the well known approach on finite graphs and point out the main differences between the finite and infinite setting.
(joint work with M.E. Dür and F. Vallentin)
The Hirsch Conjecture: Where do we go from here? (Eddie Kim, Delft University of Technology)
Motivated by the theoretical worst-case analysis of the simplex method for linear programming, the Hirsch Conjecture asserted that the diameter of a convex polytope is bounded by its number of facets minus its dimension. In 2010, F. Santos presented a counterexample to the Hirsch Conjecture. We survey some relevant history regarding the conjecture and present a full proof of Santos' construction. Then we discuss some recent research providing evidence on the positive and negative side for conjectures which are weaker than the Hirsch Conjecture.
On the complexity of computing the handicap of a sufficient matrix (Mariann Nagy, University of Tilburg)
The class of sufficient matrices is important in the study of the linear complementarity problem (LCP) -- some interior point methods (IPMs) for LCPs with sufficient matrices have complexity polynomial in the bit size of the matrix and its handicap. We show that the handicap of a sufficient matrix may be exponential in its bit size, implying that the known complexity bounds of IPMs are not polynomial in the input size of the LCP.
Complexity results by Tseng (2000) imply, that deciding whether the handicap of a given matrix is finite is an NP-hard problem. We therefore also investigate semidefinite programming based heuristics for computing a (finite) upper bound on the handicap, if such a value exists. We show that our heuristic provides a suitable value for the so-called P-matrices (where all principle minors are positive).
(joint work with E. de Klerk)
Bounds for packings of bodies in Rˆn via the harmonic analysis of the Euclidean motion group (Fernando de Oliveira Filho, Free University Berlin)
I will discuss the problem of bounding the maximum density of a packing of rotated and translated copies of a given body T in Rˆn. A classical case of this problem occurs when T is a unit ball, this being known as the sphere-packing problem. Another interesting case is when T is a unit simplex: It is known that the maximum density of a packing of unit simplices in Rˆ3 is strictly less than 1, but only very weak upper bounds are known.
In this talk I will present a theorem that can be used to find upper bounds for the maximum density of a packing of a given body T in Rˆn. The theorem relies on the harmonic analysis of the Euclidean motion group (the group of rotations and translations of bodies in Rˆn), which is a noncommutative group. It generalizes a theorem of Cohn and Elkies that gives upper bounds for the densities of sphere-packings.
(joint work with F. Vallentin)
Bounds in network coding from the SDP method (Alberto Passuello, University of Bordeaux)
Recently, network coding arose as an area of interest in information theory. The codes which are used in this framework come from projective geometry over finite fields, and can be seen as the q-analogs of the classic codes in the Hamming space, but with several differences as well. Therefore, even for such "projective codes" it is possible to apply tools from LP and SDP in order to bound their maximal cardinality. I will introduce the subject and explain advantages and limits of the SDP approach in this space.
Computing the Grothendieck constant for some graph classes (Antonis Varvitsiotis (CWI Amsterdam))
Given a graph G=([n],E), let E(G) denote the elliptope of G, i.e., the set of vectors x \in R^E for which there exists an n-dimensional psd matrix X with diagonal 1, such that x_{i,j}=X_{i,j}, for every edge ij. Additionally, let CUT(G) denote the cut polytope of a graph G, in +1,-1 variables. It is easy to verify, that for any graph G, CUT(G) is contained in E(G). The dilation ratio min{ K : E(G) \subseteq K CUT(G) } is called the Grothendieck constant of G. This graph parameter was introduced by Alon et al. and has proven to be extreme fruitful for an abundance of applications, most notably in approximation algorithms and quantum information theory.
In this talk I will survey selected results from the recent literature. Moreover, I will present a closed formula for the Grothendieck constant of K5 minor free graphs, in terms of their girth, and I will give tight upper bounds for some other graph classes.
(joint work with M. Laurent)
Program
10h30-11h00 Fernando de Oliveira Filho
11h15-11h45 Alberto Passuello
12h00-12h30 Mariann Nagy
12h30-14h00 lunch break
14h00-14h30 Peter Dickinson
14h45-15h15 Cristian Dobre
15h30-16h00 Antonis Varvitsiotis
16h15-16h45 Eddie Kim