# About the Max-Cut SDP

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?

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}$.
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).