About the Max-Cut SDP

Question

The Max-Cut optimization problem on a graph $G=(V,E)$ can be written as the question of wanting to maximize the function $\frac{1}{4} \sum_{(i,j) \in E } (x_i -x_j)^2$ under the constraint $x_i^2 = 1, x_i \in \mathbb{R}, \forall i \in V$.

Now the usual SDP relaxation is to lift the $x_i$s to vectors $\vec{x_i} \in \mathbb{R}^d$ for some $d$ with the new objective function to be maximized being $\frac{1}{4} \sum_{(i,j) \in E } \vert \vert \vec{x_i} - \vec{x_j} \vert\vert _2 ^2$ under the new constraint being $\vert \vert \vec{x_i} \vert \vert _2 ^2 = 1$.

• I wonder why in the usual SDP relaxation we use the $l_2$ norm. Is that just convenience or is there some optimality argument about it? Like one could have as well for any $4$ integers $p,q,r,s$ thought of,

maximizing $\sum_{(i,j) \in E } \vert \vert \vec{x_i} - \vec{x_j} \vert\vert _p ^q$ under the constraint being $\vert \vert \vec{x_i} \vert \vert _r ^s = 1$.

I believe this optimization problem would still give the max-cut?

Beyond the fact that such an optimization would probably be very hard to do, is there any fundamental reason why we do not do such a formulation of optimizing the $q^{th}$ power of the $p-norm$ under a constraint fixing the $s^{th}$-power of the $r-norm$?

• (will there emerge constraints on the integers $p,q,r,s$ for this to work?)

---

For example,

Even before the relaxation one could have as well written the optimization question as wanting to optimize $\frac{1}{16} \sum_{(i,j) \in E } (x_i -x_j)^4$ under the constraint $x_i^2 = 1, x_i \in \mathbb{R}, \forall i \in V$. I believe this would still give the same max-cut!

And then one might have thought of its "natural" SDP relaxation to be,

maximizing $\frac{1}{16} \sum_{(i,j) \in E } \vert \vert \vec{x_i} - \vec{x_j} \vert\vert _4 ^4$ under the constraint being $\vert \vert \vec{x_i} \vert \vert _2 ^2 = 1$.

• Do we know that say the above SDP won't beat the $0.878$ factor?

Answer 1

An SDP relaxation is not an arbitrary optimization problem; rather, it consists of optimizing a linear function over semidefinite and linear constraints. One general formulation of SDP is $$ \begin{align*} &\max \sum_{ij} c_{ij} x_{ij} \\ s.t. \;\;& X \succeq 0 \\ & A \mathbf{x} = \mathbf{b} \end{align*} $$ Here $X$ is the matrix whose entries are $x_{ij}$, and $\mathbf{x}$ is a vector whose entries are $x_{ij}$ (in some arbitrary order).

Standard accounts on semidefinite programming should explain why the SDP relaxation that you describe can indeed be formulated in this form. In short, the idea is that $x_{ij}$ is going to represent the inner product $\langle \vec{x}_i, \vec{x}_j \rangle$. The fact that $X$ is positive semidefinite is equivalent to the existence of such vectors $\vec{x}_i$. The objective function $\sum_{(i,j) \in E} \|\vec{x}_i - \vec{x}_j\|^2$ can be written as a linear combination of the $x_{ij}$, and the constraints $\|\vec{x}_i\| = 1$ can be written as linear constraints on the $x_{ij}$.

Why do we care about semidefinite programs? Because we know that they can be solved (approximately, but arbitrarily well) in polynomial time. This is not true for an arbitrary optimization problem.

There is some evidence that the Goemans–Williamson constant $0.878$ is best-possible for polynomial time algorithms. Namely, this is the case if Khot's Unique Games Conjecture holds. Under this conjecture, Raghavendra showed that SDP relaxations are optimal for a wide class of problems (constraint satisfaction problems).