Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting

Florian Jarre (), Felix Lieder, Ya-Feng Liu and Cheng Lu
Additional contact information
Florian Jarre: Mathematisches Institut, Heinrich Heine University
Felix Lieder: Mathematisches Institut, Heinrich Heine University
Ya-Feng Liu: Chinese Academy of Sciences
Cheng Lu: School of Economics and Management, North China Electric Power University

Journal of Global Optimization, 2020, vol. 76, issue 4, No 13, 913-932

Abstract: Abstract This paper considers a generalization of the “max-cut-polytope” $$\hbox {conv}\{\ xx^T\mid x\in {\mathbb {R}}^n, \ \ |x_k| = 1 \ \hbox {for} \ 1\le k\le n\}$$conv{xxT∣x∈Rn,|xk|=1for1≤k≤n} in the space of real symmetric $$n\times n$$n×n-matrices with all-one diagonal to a complex “unit modulus lifting” $$\hbox {conv}\{xx^*\mid x\in {\mathbb {C}}^n, \ \ |x_k| = 1 \ \hbox {for} \ 1\le k\le n\}$$conv{xx∗∣x∈Cn,|xk|=1for1≤k≤n} in the space of complex Hermitian $$n\times n$$n×n-matrices with all-one diagonal. The unit modulus lifting arises in applications such as digital communications and shares similar symmetry properties as the max-cut-polytope. Set-completely positive representations of both sets are derived and the relation of the complex unit modulus lifting to its semidefinite relaxation is investigated in dimensions 3 and 4. It is shown that the unit modulus lifting coincides with its semidefinite relaxation in dimension 3 but not in dimension 4. In dimension 4 a family of deep valid cuts for the unit modulus lifting is derived that could be used to strengthen the semidefinite relaxation. It turns out that the deep cuts are also implied by a second lifting that could be used alternatively. Numerical experiments are presented comparing the first lifting, the second lifting, and the unit modulus lifting for $$n=4$$n=4.

Keywords: Max-cut problem; Complex variables; Semidefinite relaxation; Unit modulus lifting (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-019-00813-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:76:y:2020:i:4:d:10.1007_s10898-019-00813-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-019-00813-x

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().