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

doi:10.1007/s10898-019-00813-x

CSpace

	Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting
	Jarre, Florian 1; Lieder, Felix 1; Liu, Ya-Feng 2; Lu, Cheng 3
	2020-04-01
发表期刊	JOURNAL OF GLOBAL OPTIMIZATION
ISSN	0925-5001
卷号	76 期号:4 页码:913-932
摘要	This 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.
关键词	Max-cut problem Complex variables Semidefinite relaxation Unit modulus lifting
DOI	10.1007/s10898-019-00813-x
收录类别	SCI
语种	英语
WOS研究方向	Operations Research & Management Science ; Mathematics
WOS类目	Operations Research & Management Science ; Mathematics, Applied
WOS记录号	WOS:000520855000013
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/50983
专题	中国科学院数学与系统科学研究院
通讯作者	Jarre, Florian
作者单位	1.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
推荐引用方式 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.