Optimization Online


Set-Completely-Positive Representations and Cuts for the Max-Cut Polytope and the Unit Modulus Lifting

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\in\real^n, \ \ |x_k| = 1 \ \hbox{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\in\complex^n, \ \ |x_k| = 1 \ \hbox{for} \ 1\le k\le n\}$ in the space of complex Hermitian $n\times n$-matrices with all-ones-diagonal. The unit modulus lifting arises in applications such as digital communication 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 strengthen the semidefinite relaxation, and also an extension to sharper convex quadratic cuts is derived which yields an optimal approximation to the boundary of the unit modulus lifting.

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: Journal of Global Optimization, (2019) https://doi.org/10.1007/s10898-019-00813-x


Entry Submitted: 11/06/2017
Entry Accepted: 11/06/2017
Entry Last Modified: 07/29/2019

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