246. Semidefinite liftings for the complex cut polytope
Invited abstract in session WC-2: Conic and Semidefinite Optimization, stream Conic optimization: theory, algorithms and applications.
Wednesday, 10:05 - 11:20Room: M:O
Authors (first author is the speaker)
| 1. | Miguel Anjos
|
| School of Mathematics, University of Edinburgh | |
| 2. | Lennart Sinjorgo
|
| Tilburg University | |
| 3. | Renata Sotirov
|
| Tilburg University |
Abstract
We consider the complex cut polytope: the convex hull of Hermitian rank-one matrices xx*, where the elements of the n-dimensional vector x are complex m-th unit roots. These polytopes find applications in MAX-3-CUT, digital communication, and more generally, complex quadratic programming. For m = 2, the complex cut polytope corresponds to the well-known real cut polytope. We provide an exact description of the complex cut polytope for m = n = 3 and investigate second order semidefinite liftings of the complex cut polytope. For such second order liftings, we show a method for reducing the size of the matrix, without weakening the approximation. We support our theoretical findings with numerical experiments.
Keywords
- SS - Semidefinite Optimization
Status: accepted
Back to the list of papers