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.

 

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s