## SDP and max-cut

Semi-definite programming generalizes linear programming. One standard definition of SDP is the following:

$\min C \bullet X$ such that $A_i \bullet X = b_i, \forall i$ and $X \succeq 0$.

Here $C, X, A_i, and b_i$ are all matrices and the $\bullet$ operation corresponds to entry-wise multiplication. An equivalent formulation of SDP is $\min \sum_{i,j} c_{ij} x_i \cdot x_j$ such that $\sum_{j,k} a_{ijk} x_j \cdot x_k=b_i$. So we can either view it as linear programming with matrices and a funny PSD constraint or as quadratic programming where the variables are vectors. Note that PSD matrices $X \succeq 0$ forms a convex cone in $\mathbb{R}^{n^2}$. If we simply treat it as a convex optimization problem, then everything scales as $n^2$ and is not efficient.

MAX-CUT. Given a graph $G = (E, V)$ with weight $w_{ij}$ on edge $e_{ij}$, the goal is to partition the vertices into two sets so that the sum of the crossing edges is maximized. This is a NP-hard problem and can be formulated as an integer program. Assign a binary variable $x_i$ to each vertex such that $x_i = 1$ if $i$ belongs to the left partition and $x_i = -1$ otherwise. Then MAX-CUT is equivalent to:

$\max \sum_{i,j} w_{ij} (1 - x_ix_j)$ such that $x_i^2 = 1$.

As a relaxation, let $x_i$ be a vector in $\mathbb{R}^n$, and solve the following SDP:

$\min w_{ij} x_i \cdot x_j$ such that $x_i \cdot x_i = 1$. The solutions $x_i$ are vectors on the unit sphere. We think of the vector $x_i$ as representing the node $i$ in some $n$-dim feature space and $x_i \cdot x_j$ as measuring the similarity between the two points. Is there a way to interpret these features?

To derive a hard partition, we randomly select a hyperplane and put all the vectors on the one side of the hyperplane into one partition. The neat thing is that the probability of $x_i, x_j$ being separated by the hyperplane is quite close to $0.5 - 0.5 x_i \cdot x_j$. So the randomized rounding is close to the optimal of the SDP, which is guaranteed to be better than the maximum MAX-CUT value. Truly an amazing algorithm.