Cuts and semidefinite liftings for the complex cut polytope

Abstract

We consider the complex cut polytope: the convex hull of Hermitian rank 1 matrices $x{x}^{\mathrm{H}}$, where the elements of $x\in {\mathbb{C}}^n$ are $m$th unit roots. These polytopes have applications in $\text{MAX-3-CUT}$, digital communication technology, angular synchronization and more generally, complex quadratic programming. For $m=2$, the complex cut polytope corresponds to the well-known cut polytope. We generalize valid cuts for this polytope to cuts for any complex cut polytope with finite $m>2$ and provide a framework to compare them. Further, we consider a second semidefinite lifting of the complex cut polytope for $m=\infty$. This lifting is proven to be equivalent to other complex Lasserre-type liftings of the same order proposed in the literature, while being of smaller size. Our theoretical findings are supported by numerical experiments on various optimization problems.

29 pages (including references) + 6 pages appendix