Preview

PDF, English - main document Download (1MB) | Terms of use

Abstract

The thesis follows two main goals. The first is to formulate, explain and link representations of partitions that can be used to model partition problems. The second is to use the method of moments, an approach from polynomial optimization, to bound the global optima of the corresponding partition problems by constructing convex relaxations of these representations. For problems like Euclidean k-clustering, this is a stark contrast to their usual treatment, which mostly involves heuristics that are content with local optima. Since the method of moments results in a convex approach, the focus lies on finding and exploiting representations that lack a non-trivial symmetry-invariant solution space in order to be able to round the relaxations to feasible solutions.

The representations considered in the thesis are assignment matrices, partition matrices, projection matrices and simplicial covers for a generalized version of Euclidean k-clustering. Connections and transformations between the matrix classes are established and compared to the literature, and it is explicitly shown how partition matrices arise naturally from assignment matrices through the method of moments.

Using projection matrices, we are able to give a new formulation of the colouring number, and the resulting relaxations from the method of moments are compared to the Lovász theta number. We characterize under which circumstances the relaxations agree and explain when they do not, indicating our first main result that in this case, relaxing binary matrix entries yields better results than relaxing binary eigenvalues.

The final part of the thesis is devoted to what we call the affine Euclidean k-clustering problem, which is a more general version of the Euclidean k-clustering problem. As our second main result of the thesis, we introduce a new method for this challenging problem, utilizing simplicial covers of the feasible region to formulate unique representations of the optimal solutions of the underlying problem. In contrast to applying the method of moments directly, applying it to our formulation yields a slower growth in size, better parallelizability and enables us to recover information that can be used for rounding, which is not possible for the standard formulation due to symmetry.