CSpace
Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting
Jarre, Florian1; Lieder, Felix1; Liu, Ya-Feng2; Lu, Cheng3
2020-04-01
Source PublicationJOURNAL OF GLOBAL OPTIMIZATION
ISSN0925-5001
Volume76Issue:4Pages:913-932
AbstractThis paper considers a generalization of the "max-cut-polytope" conv{xxT divide x is an element of Rn,|xk|=1for1 <= k <= n}in the space of real symmetric nxnmatrices with all-one diagonal to a complex "unit modulus lifting" conv{xx* divide x is an element of Cn,|xk|=1for1 <= k <= n}in the space of complex Hermitian nxn-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.
KeywordMax-cut problem Complex variables Semidefinite relaxation Unit modulus lifting
DOI10.1007/s10898-019-00813-x
Indexed BySCI
Language英语
WOS Research AreaOperations Research & Management Science ; Mathematics
WOS SubjectOperations Research & Management Science ; Mathematics, Applied
WOS IDWOS:000520855000013
PublisherSPRINGER
Citation statistics
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/50983
Collection中国科学院数学与系统科学研究院
Corresponding AuthorJarre, Florian
Affiliation1.Heinrich Heine Univ, Math Inst, Dusseldorf, Germany
2.Chinese Acad Sci, Acad Math & Syst Sci, Inst Computat Math & Sci Engn Comp, State Key Lab Sci & Engn Comp, Beijing, Peoples R China
3.North China Elect Power Univ, Sch Econ & Management, Beijing 102206, Peoples R China
Recommended Citation
GB/T 7714
Jarre, Florian,Lieder, Felix,Liu, Ya-Feng,et al. Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting[J]. JOURNAL OF GLOBAL OPTIMIZATION,2020,76(4):913-932.
APA Jarre, Florian,Lieder, Felix,Liu, Ya-Feng,&Lu, Cheng.(2020).Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting.JOURNAL OF GLOBAL OPTIMIZATION,76(4),913-932.
MLA Jarre, Florian,et al."Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting".JOURNAL OF GLOBAL OPTIMIZATION 76.4(2020):913-932.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Jarre, Florian]'s Articles
[Lieder, Felix]'s Articles
[Liu, Ya-Feng]'s Articles
Baidu academic
Similar articles in Baidu academic
[Jarre, Florian]'s Articles
[Lieder, Felix]'s Articles
[Liu, Ya-Feng]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Jarre, Florian]'s Articles
[Lieder, Felix]'s Articles
[Liu, Ya-Feng]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.