Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting
文献类型：期刊论文
| 作者 | Jarre, Florian2; Lieder, Felix2; Liu, Ya-Feng1; Lu, Cheng3 |
| 刊名 | JOURNAL OF GLOBAL OPTIMIZATION
 |
| 出版日期 | 2020-04-01 |
| 卷号 | 76期号:4页码:913-932 |
| 关键词 | Max-cut problem Complex variables Semidefinite relaxation Unit modulus lifting |
| ISSN号 | 0925-5001 |
| DOI | 10.1007/s10898-019-00813-x |
| 英文摘要 | 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. |
| WOS研究方向 | Operations Research & Management Science ; Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:000520855000013 |
| 出版者 | SPRINGER |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/50982]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | Jarre, Florian |
| 作者单位 | 1.Chinese Acad Sci, Acad Math & Syst Sci, Inst Computat Math & Sci Engn Comp, State Key Lab Sci & Engn Comp, Beijing, Peoples R China 2.Heinrich Heine Univ, Math Inst, Dusseldorf, Germany 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. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。