\(\)
We consider the complex cut polytope: the convex hull of Hermitian rank 1 matrices \(xx^{\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. We also prove that a second semidefinite lifting of the complex cut polytope for \(n = m=3\) is exact. Our theoretical findings are supported by numerical experiments on various optimization problems.
Citation
sinjorgo2024_complexCutPolytope
Article
View Cuts and semidefinite liftings for the complex cut polytope