Optimization Online


The Max-Cut Polytope, the Unit Modulus Lifting, and their set-completely-positive representations

Florian Jarre(jarre***at***hhu.de)
Felix Lieder(Felix.lieder***at***hhu.de)
Ya-Feng Liu(yafliu***at***lsec.cc.ac.cn)
Cheng Lu(lucheng1983***at***163.com)

Abstract: This paper considers a generalization of the ``max-cut-polytope'' $\conv\{xx^T\mid |x_k| = 1$ for $1\le k\le n\}$ in the space of real symmetric $n\times n$-matrices with all-ones-diagonal to a complex ``unit modulus lifting'' $\conv\{xx\HH\mid |x_k| = 1$ for $1\le k\le n\}$ in the space of complex Hermitian $n\times n$-matrices with all-ones-diagonal. 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.

Keywords: Max-cut problem, complex variables, semidefinite relaxation, unit modulus lifting.

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Other )

Citation: Research Report, Nov. 2017

Download: [PDF]

Entry Submitted: 11/06/2017
Entry Accepted: 11/06/2017
Entry Last Modified: 11/06/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society