Cuts and semidefinite liftings for the complex cut polytope

Lennart Sinjorgo, Renata Sotirov, Miguel F Anjos

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

We consider the complex cut polytope: the convex hull of Hermitian rank 1 matrices xxH, where the elements of x∈Cn are mth unit roots. These polytopes have applications in 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=∞. 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.
Original languageEnglish
JournalMathematical programming
Publication statusPublished - 5 Sept 2024

Fingerprint

Dive into the research topics of 'Cuts and semidefinite liftings for the complex cut polytope'. Together they form a unique fingerprint.

Cite this