How to write Goemans-Williamson MAX-CUT relaxation as SDP

Question

Let W be a graph Laplacian (symmetric diagonally dominant, and thus PSD), and X the matrix variable.

Let $<A,B>=Tr(A^TB)$.

$$\text{Maximize}\;\; \displaystyle\sum_{i,j} w_{ij}(x^{(i)}\cdot x^{(j)})$$ $$\text{Subject to}\;\; x^{(i)}\cdot x^{(i)}=1$$

I want to write this in standard semidefinite programming form. The best I've been able to do is

$$\text{Maximize}\;\; <W, X^TX>$$ $$\text{Subject to}\;\; <A_i, X^TX>=1$$

where $A_i$ is a matrix of zeros except for a $1$ at the $i^{th}$ slot on its diagonal, and where $X^TX$ is automatically PSD. If I replace $X^TX$ with $S$ in the above SDP and require that it be PSD, then I can clearly optimize with $S$ as my variable, but there may be no $X^{*}$ which corresponds to $S^{*}$, and if there is, it's not clear how I would recover it.

Also, I'm curious what about the Laplacian ensures the convexity of $\sum_{i,j} w_{ij}(x^{(i)}\cdot x^{(j)})$, is it just the fact that it's PSD, or does it need to be diagonally dominant?

Answer 1

A common definition of "positive semidefinite" is:

A real symmetric $n$ by $n$ matrix $S$ is positive semidefinite if and only if

$z^{T}Sz \geq 0$ for all $z \in R^{n}$.

Another equivalent definition is that a real symmetric $n$ by $n$ matrix $S$ is positive semidefinite if and only if all of its eigenvalues are non-negative. I won't go through the proof that these two definitions are equivalent (it's in lots of textbooks.)

A third equivalent definition that is not quite so well known is:

A real symmetric $n$ by $n$ matrix $S$ is positive semidefinite if and only if there is a real $n$ by $n$ matrix $X$ such that

$S=X^{T}X$.

To show that that this last definition is equivalent,

If $S$ is positive semidefinite, then we diagonalize $S$ as

$S=U \Lambda U^{T}$

where $U$ is orthogonal and $\Lambda$ is diagonal with non-negative elements on the diagonal. By taking the square roots of these non-negative diagonal elements, we can construct a diagonal matrix square root of $\Lambda$, $\Lambda^{1/2}$. We can then write $S$ as

$S=U \Lambda^{1/2} U^{T} U \Lambda^{1/2} U^{T}$.

Let $X=U \Lambda^{1/2} U^{T}$. Note that $X$ is symmetric. Thus

$S=XX=X^{T}X$.

Computationally, we can get the matrix square root $X$ from $S$ by computing the eigenvalue decomposition of $S$. In MATLAB, there's a sqrtm() function that does the work for you.

Conversely, suppose that $S$ is a real and symmetric $n$ by $n$ matrix with

$S=X^{T}X$.

Then for any $z \in R^{n}$,

$z^{T}Sz=z^{T}X^{T}Xz=\| Xz \|_{2}^{2} \geq 0$.

Thus $S$ is positive semidefinite.

To answer your last question,

$<W, S>$

is linear in the elements of $S$ and is thus a convex (and concave) function of $S$.