Lecture 14: Semidefinite Relaxations and Max-Cut
Convex relaxation, Gaussian rounding, and the Goemans–Williamson algorithm
The last four lectures used Gaussian vectors to study suprema of random functions. This lecture uses them for something different: to solve, or nearly solve, a hard combinatorial optimization problem. The problem is to maximize a quadratic form over the vertices of the discrete cube \(\{-1,1\}^n\). A union bound over \(2^n\) points is useless here, and the tools are instead convex relaxation, which replaces the cube by a convex set of matrices, and randomized rounding, which uses a Gaussian vector to map a point of the convex set back to the cube. The analysis of the rounding step is a single identity about the signs of two correlated Gaussians, and the identity is exactly what Grothendieck’s inequality, in the next lecture, is built around.
1 Quadratic optimization over the cube
Let \(A\) be a symmetric \(n\times n\) real matrix. The problem is \[ \mathrm{INT}(A):=\max\Big\{\sum_{i,j=1}^nA_{ij}x_ix_j:\ x\in\{-1,1\}^n\Big\} =\max_{x\in\{-1,1\}^n}\langle Ax,x\rangle . \] The feasible set has \(2^n\) points, and exhaustive search is exponential. No essentially faster exact method is expected to exist, because the problem is NP-hard. The standard witness to its hardness is the maximum cut problem for graphs.
Definition 1 (Maximum cut) Let \(G=(V,E)\) be a finite simple undirected graph on \(V=\{1,\ldots,n\}\) with adjacency matrix \(A\), so \(A_{ij}=1\) if \(\{i,j\}\in E\) and \(A_{ij}=0\) otherwise. A partition of \(V\) into two sets is encoded by a vector \(x\in\{-1,1\}^n\), and its cut is the number of edges joining the two sets, \[ \mathrm{CUT}(G,x):=\#\big\{\{i,j\}\in E:\ x_i\neq x_j\big\} =\frac14\sum_{i,j=1}^nA_{ij}(1-x_ix_j). \] The maximum cut is \(\mathrm{MAX\text{-}CUT}(G):=\max_{x\in\{-1,1\}^n}\mathrm{CUT}(G,x)\).
The formula for \(\mathrm{CUT}(G,x)\) holds because \(1-x_ix_j\) is \(2\) when \(x_i\neq x_j\) and \(0\) otherwise, and each edge is counted twice in the double sum. Expanding, \(\mathrm{CUT}(G,x)=\frac12|E|-\frac14\langle Ax,x\rangle\), so the maximum cut is the problem \(\mathrm{INT}(-A)\) up to an additive constant. Computing \(\mathrm{MAX\text{-}CUT}(G)\) exactly is NP-hard, which we take as known.
Since exact solutions are out of reach, the goal is an approximation algorithm: an efficient procedure that produces a cut of size at least \(\alpha\cdot\mathrm{MAX\text{-}CUT}(G)\) for some constant \(\alpha<1\), on every graph. The first such algorithm needs no ideas at all.
Proposition 1 (A random cut) Let \(x\) be uniformly distributed on \(\{-1,1\}^n\). Then \[ \mathbb E\,\mathrm{CUT}(G,x)=\frac12|E|\geq\frac12\mathrm{MAX\text{-}CUT}(G). \]
The coordinates of \(x\) are independent symmetric signs, so \(\mathbb Ex_ix_j=0\) for \(i\neq j\), and \(A_{ii}=0\) because the graph has no loops. Taking expectations in the formula for \(\mathrm{CUT}(G,x)\) leaves \(\frac14\sum_{i,j}A_{ij}=\frac12|E|\). The inequality is \(\mathrm{MAX\text{-}CUT}(G)\leq|E|\).
A random partition cuts half the edges on average, so it is a \(\frac12\)-approximation in expectation. Repeating the experiment a few times and keeping the best cut gives a \((\frac12-\varepsilon)\)-approximation with high probability. Doing better requires looking at the graph.
2 The semidefinite relaxation
The idea of relaxation is to enlarge the feasible set to a convex one over which the maximum can be computed, and then to argue that the enlargement does not increase the maximum by much. For \(\mathrm{INT}(A)\), the natural enlargement replaces each sign \(x_i\in\{-1,1\}\), a unit vector in \(\mathbb R^1\), by a unit vector \(X_i\) in \(\mathbb R^n\): \[ \mathrm{SDP}(A):=\max\Big\{\sum_{i,j=1}^nA_{ij}\langle X_i,X_j\rangle:\ X_1,\ldots,X_n\in S^{n-1}\Big\}. \] Taking \(X_i=x_ie_1\) shows \(\mathrm{INT}(A)\leq\mathrm{SDP}(A)\). The name comes from a reformulation in terms of the Gram matrix of the \(X_i\).
Lemma 1 (Gram matrices of unit vectors) An \(n\times n\) matrix \(X\) is the Gram matrix \(X_{ij}=\langle X_i,X_j\rangle\) of some unit vectors \(X_1,\ldots,X_n\in\mathbb R^n\) if and only if \(X\) is positive semidefinite with \(X_{ii}=1\) for every \(i\). The vectors can be read off from \(X\) as the columns of \(X^{1/2}\).
If \(X_{ij}=\langle X_i,X_j\rangle\) then \(X=M^{\mathsf T}M\) with \(M\) the matrix whose columns are the \(X_i\), so \(\langle Xa,a\rangle=\|Ma\|_2^2\geq0\), and \(X_{ii}=\|X_i\|_2^2=1\). Conversely, if \(X\succeq0\) with unit diagonal, let \(M=X^{1/2}\) be the positive semidefinite square root. Then \(X=M^{\mathsf T}M\), so \(X_{ij}\) is the inner product of the \(i\)-th and \(j\)-th columns of \(M\), and these columns are unit vectors because \(X_{ii}=1\).
Writing \(\langle A,X\rangle:=\operatorname{tr}(A^{\mathsf T}X)=\sum_{ij}A_{ij}X_{ij}\) for the trace inner product on matrices, the lemma gives \[ \mathrm{SDP}(A)=\max\big\{\langle A,X\rangle:\ X\succeq0,\ X_{ii}=1\text{ for all }i\big\}. \] This is a maximization of a linear function over the intersection of the convex cone of positive semidefinite matrices with an affine subspace, which is a convex set. In particular the maximum exists, since the feasible set is compact.
Definition 2 (Semidefinite program) A semidefinite program is an optimization problem of the form \[ \text{maximize }\langle A,X\rangle\quad\text{subject to}\quad X\succeq0,\ \ \langle B_k,X\rangle=b_k\ \ (k=1,\ldots,m), \] where \(A,B_1,\ldots,B_m\) are given symmetric matrices and \(b_1,\ldots,b_m\) are given reals.
The relaxation \(\mathrm{SDP}(A)\) is the case \(B_k=e_ke_k^{\mathsf T}\), \(b_k=1\). Semidefinite programs are convex programs, and they can be solved to any prescribed accuracy in time polynomial in \(n\) and in the number of accuracy digits, for instance by interior point methods. We treat this as a black box: the value \(\mathrm{SDP}(A)\) and a maximizing configuration \((X_i)\) are available.
Two things remain. First, how much larger than \(\mathrm{INT}(A)\) can \(\mathrm{SDP}(A)\) be? Second, given a maximizing configuration of unit vectors, how does one produce a point of the cube? The second question is answered by a Gaussian vector, and its analysis answers the first.
3 Rounding by a random hyperplane
Let \(X_1,\ldots,X_n\in S^{n-1}\) be given. Choose \(g\sim N(0,I_n)\) and set \[ x_i:=\operatorname{sgn}\langle X_i,g\rangle, \qquad i=1,\ldots,n . \] Geometrically, the hyperplane \(g^\perp\) splits the sphere into two hemispheres, and \(x_i\) records which hemisphere contains \(X_i\). Two vectors that are close on the sphere are likely to land on the same side, so the rounding respects the geometry of the configuration. The following identity quantifies this.
Lemma 2 (Grothendieck’s identity) Let \(g\sim N(0,I_n)\) and let \(u,v\in S^{n-1}\). Then \[ \mathbb E\operatorname{sgn}\langle g,u\rangle\operatorname{sgn}\langle g,v\rangle =\frac2\pi\arcsin\langle u,v\rangle . \]
Let \(\theta\in[0,\pi]\) be the angle between \(u\) and \(v\), so \(\langle u,v\rangle=\cos\theta\). By the rotation invariance of \(g\) (Lecture 10) we may assume \(u=e_1\) and \(v=\cos\theta\,e_1+\sin\theta\,e_2\). Then \(\langle g,u\rangle=g_1\) and \(\langle g,v\rangle=g_1\cos\theta+g_2\sin\theta\) depend only on the planar vector \((g_1,g_2)\), which is rotation invariant in \(\mathbb R^2\), so its direction is uniform on the circle.
The signs of \(\langle g,u\rangle\) and \(\langle g,v\rangle\) differ exactly when \((g_1,g_2)\) lies on opposite sides of the two lines \(u^\perp\) and \(v^\perp\) through the origin. These lines make an angle \(\theta\), and they divide the plane into four sectors, of which the two where the signs differ have angles \(\theta\) and \(\theta\). Hence \[ \mathbb P\big\{\operatorname{sgn}\langle g,u\rangle\neq\operatorname{sgn}\langle g,v\rangle\big\}=\frac{2\theta}{2\pi}=\frac\theta\pi , \] and the product of the signs has expectation \(1-2\theta/\pi=\frac2\pi\big(\frac\pi2-\theta\big)=\frac2\pi\arcsin(\cos\theta)\). The event \(\langle g,u\rangle=0\) has probability zero and does not affect the computation.
Compare the identity \(\mathbb E\langle g,u\rangle\langle g,v\rangle=\langle u,v\rangle\) of Lecture 10. Taking signs replaces the linear function \(t\mapsto t\) by the nonlinear \(t\mapsto\frac2\pi\arcsin t\), which agrees with the linear function at \(t=\pm1\), lies below it on \((0,1)\), and above it on \((-1,0)\). Everything in the analysis of rounding, and in Grothendieck’s inequality, is about the gap between these two functions.
4 The Goemans–Williamson algorithm
For the maximum cut problem, the relaxation is \[ \mathrm{SDP}(G):=\max\Big\{\frac14\sum_{i,j}A_{ij}\big(1-\langle X_i,X_j\rangle\big):\ X_i\in S^{n-1}\Big\} \geq\mathrm{MAX\text{-}CUT}(G), \] which is a semidefinite program by Lemma 1. The algorithm is: solve the relaxation, then round the solution by a random hyperplane.
The analysis needs one numerical fact. Define \[ \alpha:=\min_{0<\theta\leq\pi}\frac2\pi\cdot\frac\theta{1-\cos\theta}. \] The function being minimized tends to \(+\infty\) as \(\theta\downarrow0\), since \(1-\cos\theta\sim\theta^2/2\), and equals \(1\) at \(\theta=\pi\), so the minimum exists and is positive. It is attained at the unique solution of \(1-\cos\theta=\theta\sin\theta\) in \((0,\pi)\), which is \(\theta\approx2.33\), and its value is \[ \alpha\approx0.8786 . \] Substituting \(t=\cos\theta\), the definition of \(\alpha\) says precisely that \[ \frac2\pi\arccos t\geq\alpha(1-t) \qquad\text{for all }t\in[-1,1] . \tag{1}\]
Theorem 1 (Goemans–Williamson) Let \(G\) be a graph with adjacency matrix \(A\), let \((X_i)\) be a maximizer of \(\mathrm{SDP}(G)\), and let \(x=(\operatorname{sgn}\langle X_i,g\rangle)_i\) be its rounding by a random hyperplane. Then \[ \mathbb E\,\mathrm{CUT}(G,x)\geq\alpha\cdot\mathrm{SDP}(G)\geq\alpha\cdot\mathrm{MAX\text{-}CUT}(G), \qquad\alpha\approx0.8786 . \]
By the cut formula, linearity of expectation, and Lemma 2, \[ \mathbb E\,\mathrm{CUT}(G,x)=\frac14\sum_{i,j}A_{ij}\big(1-\mathbb Ex_ix_j\big) =\frac14\sum_{i,j}A_{ij}\Big(1-\frac2\pi\arcsin\langle X_i,X_j\rangle\Big) =\frac14\sum_{i,j}A_{ij}\,\frac2\pi\arccos\langle X_i,X_j\rangle . \] Every \(A_{ij}\) is nonnegative, so Equation 1 may be applied term by term: \[ \mathbb E\,\mathrm{CUT}(G,x)\geq\alpha\cdot\frac14\sum_{i,j}A_{ij}\big(1-\langle X_i,X_j\rangle\big)=\alpha\cdot\mathrm{SDP}(G). \] The second inequality is \(\mathrm{SDP}(G)\geq\mathrm{MAX\text{-}CUT}(G)\).
Several remarks.
The bound is in expectation, but that is enough. The random variable \(\mathrm{CUT}(G,x)\) takes values in \([0,|E|]\), so \(\mathbb P\{\mathrm{CUT}(G,x)\geq(\alpha-\varepsilon)\mathrm{SDP}(G)\}\geq c\varepsilon\) for a constant \(c\) depending on \(|E|/\mathrm{SDP}(G)\leq2\), by the reverse Markov inequality. Repeating the rounding \(O(\varepsilon^{-1}\log(1/\eta))\) times and keeping the best cut therefore gives an \((\alpha-\varepsilon)\)-approximation with probability at least \(1-\eta\). The rounding can also be derandomized, but the random version is the natural one.
Where the constant comes from. The relaxation loses nothing on the constraint side, since the cube is contained in the feasible set. All of the loss is in the rounding step, and it is measured by the ratio of \(\frac2\pi\arccos t\) to \(1-t\) in Equation 1. The worst case is an edge whose endpoints make angle \(\theta\approx2.33\) in the relaxed solution, for which the hyperplane cuts the edge with probability \(\theta/\pi\approx0.74\) while the relaxation counts it with weight \((1-\cos\theta)/2\approx0.85\).
The constant is believed optimal. Håstad proved that no polynomial time algorithm achieves a ratio above \(16/17\approx0.941\) unless P equals NP, and Khot, Kindler, Mossel and O’Donnell (Khot et al. 2007) showed that under the Unique Games Conjecture no polynomial time algorithm achieves a ratio above \(\alpha\) itself. The random hyperplane is then the best possible rounding of the best possible relaxation. The algorithm is due to Goemans and Williamson (Goemans and Williamson 1995).
5 Beyond max-cut
The argument used two features of the cut objective: the coefficients \(A_{ij}\) are nonnegative, and the objective involves \(1-\langle X_i,X_j\rangle\) rather than \(\langle X_i,X_j\rangle\) alone. Both fail for the general problem \(\mathrm{INT}(A)\). For a symmetric \(A\) with entries of both signs, rounding a maximizer \((X_i)\) of \(\mathrm{SDP}(A)\) gives \[ \mathbb E\langle Ax,x\rangle=\frac2\pi\sum_{i,j}A_{ij}\arcsin\langle X_i,X_j\rangle , \] and there is no termwise inequality relating \(\arcsin\langle X_i,X_j\rangle\) to \(\langle X_i,X_j\rangle\) that respects the signs of the coefficients. If the nonlinearity were absent, that is, if \(\arcsin t\) could be replaced by \(t\), we would have \(\mathbb E\langle Ax,x\rangle=\frac2\pi\mathrm{SDP}(A)\), and hence \(\mathrm{INT}(A)\geq\frac2\pi\mathrm{SDP}(A)\) for every \(A\).
Whether some inequality of this form holds, \(\mathrm{SDP}(A)\leq K\cdot\mathrm{INT}(A)\) with a constant \(K\) independent of \(A\) and \(n\), is not at all obvious. The statement that it does is Grothendieck’s inequality, and the next lecture proves it by a device that removes the nonlinearity: the vectors \(X_i\) are replaced by vectors \(\Phi(X_i)\) in a larger Hilbert space, chosen so that the arcsine of their inner products is a linear function of the original inner products. The rounding then becomes exact, and the Gaussian vector used to round is the isonormal process of Lecture 10 on the larger space.
The same question arises for the bilinear problem \[ \max\Big\{\sum_{i,j}A_{ij}x_iy_j:\ x\in\{-1,1\}^m,\ y\in\{-1,1\}^n\Big\}, \] whose value is the cut norm of \(A\), a quantity that governs the regularity of graphs and the approximation of dense combinatorial problems. Its semidefinite relaxation, over unit vectors \(X_i\) and \(Y_j\), is the setting in which Grothendieck’s inequality is usually stated.
6 Where we go next
The next lecture states Grothendieck’s inequality, deduces from it that the bilinear relaxation is tight up to the constant \(K\), explains why the symmetric problem is genuinely harder, and proves the inequality with \(K\leq\pi/(2\log(1+\sqrt2))\approx1.78\) by Krivine’s kernel-trick argument.