Cuts and semidefinite liftings for the complex cut polytope
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909293863763968 |
|---|---|
| author | Sinjorgo, Lennart Sotirov, Renata Anjos, Miguel F. |
| author_facet | Sinjorgo, Lennart Sotirov, Renata Anjos, Miguel F. |
| contents | We consider the complex cut polytope: the convex hull of Hermitian rank 1 matrices $xx^{\mathrm{H}}$, where the elements of $x \in \mathbb{C}^n$ are $m$th unit roots. These polytopes have applications in ${\text{MAX-3-CUT}}$, digital communication technology, angular synchronization and more generally, complex quadratic programming. For ${m=2}$, the complex cut polytope corresponds to the well-known cut polytope. We generalize valid cuts for this polytope to cuts for any complex cut polytope with finite $m>2$ and provide a framework to compare them. Further, we consider a second semidefinite lifting of the complex cut polytope for $m=\infty$. This lifting is proven to be equivalent to other complex Lasserre-type liftings of the same order proposed in the literature, while being of smaller size. Our theoretical findings are supported by numerical experiments on various optimization problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_04731 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Cuts and semidefinite liftings for the complex cut polytope Sinjorgo, Lennart Sotirov, Renata Anjos, Miguel F. Optimization and Control 52B05, 60G35, 90C20, 90C22 We consider the complex cut polytope: the convex hull of Hermitian rank 1 matrices $xx^{\mathrm{H}}$, where the elements of $x \in \mathbb{C}^n$ are $m$th unit roots. These polytopes have applications in ${\text{MAX-3-CUT}}$, digital communication technology, angular synchronization and more generally, complex quadratic programming. For ${m=2}$, the complex cut polytope corresponds to the well-known cut polytope. We generalize valid cuts for this polytope to cuts for any complex cut polytope with finite $m>2$ and provide a framework to compare them. Further, we consider a second semidefinite lifting of the complex cut polytope for $m=\infty$. This lifting is proven to be equivalent to other complex Lasserre-type liftings of the same order proposed in the literature, while being of smaller size. Our theoretical findings are supported by numerical experiments on various optimization problems. |
| title | Cuts and semidefinite liftings for the complex cut polytope |
| topic | Optimization and Control 52B05, 60G35, 90C20, 90C22 |
| url | https://arxiv.org/abs/2402.04731 |