EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
582. Semidefinite liftings for the complex cut polytope
Invited abstract in session TB-38: Advances in Complex and Real Semidefinite Programming, stream Conic Optimization: Theory, Algorithms, and Applications.
Tuesday, 10:30-12:00Room: 34 (building: 306)
Authors (first author is the speaker)
| 1. | Lennart Sinjorgo
|
| Tilburg University | |
| 2. | Renata Sotirov
|
| Tilburg University | |
| 3. | Miguel Anjos
|
| School of Mathematics, University of Edinburgh |
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
- Programming, Semidefinite
- Polyhedral Combinatorics
- Telecommunications
Status: accepted
Back to the list of papers