Name
Title | ||
|---|---|---|
Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting |
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\}$$ in the space of real symmetric $$n\times 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\}$$ in the space of complex Hermitian $$n\times 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$$. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/s10898-019-00813-x | Journal of Global Optimization |
Keywords | Field | DocType |
Max-cut problem, Complex variables, Semidefinite relaxation, Unit modulus lifting | Diagonal,Combinatorics,Mathematical analysis,Modulus,Polytope,Complex variables,Hermitian matrix,Maximum cut,Mathematics | Journal |
Volume | Issue | ISSN |
76 | 4 | 0925-5001 |
Citations | PageRank | References |
1 | 0.35 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Florian Jarre | 1 | 293 | 36.75 |
| Felix Lieder | 2 | 2 | 1.85 |
| Y. F. Liu | 3 | 454 | 30.59 |
| Cheng Lu | 4 | 40 | 5.14 |