Cuts and semidefinite liftings for the complex cut polytope

• 成果类型: Article; Early Access
• 署名作者: Sinjorgo, Lennart; Sotirov, Renata; Anjos, Miguel F.
• 署名单位: Tilburg University; University of Edinburgh
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02147-3
• 发表日期: 2024
• 关键词: improved approximation algorithms; moment-sos hierarchy; polynomial optimization; quadratic optimization; relaxation; squares; Tightness; tssos; sums

摘要

We consider the complex cut polytope: the convex hull of Hermitian rank 1 matrices xx(H), where the elements of x is an element of C-n aremth unit roots. These polytopes have appli-cations in MAX-3-CUT, digital communication technology, angular synchronizationand more generally, complex quadratic programming. Form=2, the complex cutpolytope corresponds to the well-known cut polytope. We generalize valid cuts for this polytope to cuts for any complex cut poly tope with finitem>2 and provide a frame work to compare them. Further, we consider a second semi definite lifting of thecomplex cut polytope for m=infinity. This lifting is proven to be equivalent to other complex Lasserre-type liftings of the same order proposed in the literature, while beingof smaller size. Our theoretical findings are supported by numerical experiments onvarious optimization problems.