就是说我这学期为什么会学到这么个东西呢（挠头

这什么破标题（

包含一些当初做 Intro to Optimization Theory Lecture 5 的 scribing 的时候想加又没加的私货，主要参考这份 note 和另一份 slide，但我好像找不到了。虽然也很粗浅但超出了课堂讲授的和期中涉及的范围，之前本来就有一份草稿，整理出来图一乐。

Construction

Max Cut Problem

Max Cut problem 关心的是 weighted undirected graph \(G = (V,E)\)，也就是对于图上的每一条边 \((i.j)\) 都有一个对应的 weight \(w_{ij} = w_{ji}\)，来回的权重相等是无向图的设定，如果两点之间没有边相连则 \(w_{ij}=0\)，且有 \(w_{ii}=1\)（实际上没有意义，计算中也不会涉及，但在矩阵中总要写出来）。

注：很草的是，zjz 所有的 weight 都是 \(1\)，但的确不影响问题本质的理解，有 weight 的话还要多写一个参数，好累的。

在 \(G=(V,E)\) 中 \(V\) 代表点集，\(E\) 代表连边和其上权重，用 weight 构成的一个 symmetric matrix 表示。

这种图上的一个 cut 指的是点集 \(V\) 的一个子集 \(S \subseteq V\)，它实际上把点集划分为了 \(S\) 和 \(T = V\setminus S\) 两部分，而 max cut problem 所研究的就是这两部分之间所连接的边的权重和

\[W(S) \triangleq \sum_{(i,j) \in S \times T} w_{ij}\]

的最大值。

于是这个优化问题被形式化地定义为：

\[\begin{aligned}\textbf{maximize} \quad & W(S) \\ \textbf{given} \quad & G = (V,E) \end{aligned}\]

Notations

For an input graph \(G\), we denote by \(\mathrm{OPT} (G)\) the weight associated with the maxcut, i.e.

\[\mathrm{OPT} (G) = \max\{W(S) \mid S \ \text{is a subset of }V\}.\]
An \(\alpha\)-approximate max cut is a cut \(S\) s.t. \(W(S) \geq \alpha \ \mathrm{OPT}(G)\).

1/2-approximate Algorithm

一个简单的 randomized algorithm 是对图上的每一个点，以 \(1/2\) 的概率随机决定要不要把它们放进 cut 中，这样所得到的 sum of weight \(W(S)\) 的期望是：

\[\begin{aligned} E(W(S)) & = E\sum_{(i,j)\in E} w_{ij}( \textbf{1}_{i \in S,j \in T}+\textbf1_{i \in T ,j \in S}) = \sum_{(i,j)\in E} P(i\in S, j \in T) w_{ij} +P(i \in T ,j \in S)w_{ij} \\ & = \sum_{(i,j)\in E} \frac 1 2 \times \frac 1 2 \times 2w_{ij} = \frac 1 2 \sum_{(i,j) \in E} w_{ij} \end{aligned}\]

所以这至少是一个 \(1/2\)-approximate algorithm，因为 \(\sum_{(i,j) \in E} w_{ij}\) 显著大于等于 \(\mathrm{OPT}(G)\)。

Transformation into a Convex Problem

从方法的角度来说，把一个 non-convex problem 转化为 convex problem 和求解过程中需要遵循的大的原则是：

Transform the non-convex problem into convex ones through relaxation
Recover a solution from the convex problem to the non-convex one through random rounding

在这里介绍一下把 max cut problem 转化为 convex problem 和求近似解的方法。

Step 1

一个最简单的可量化的转化是：

\[\begin{aligned} \textbf{maximize} \quad & \frac 1 4 \sum_{i \in V} \sum_{j \in V}w_{ij} (1-x_ix_j) \\ \textbf{subject to} \quad & x_i \in \{+1,-1\} \end{aligned}\]

这等价于考虑

\[\begin{aligned} \textbf{maximize} \quad & \frac 1 2\sum_{(i,j) \in E} w_{ij}(1-x_ix_j) \\ \textbf{subject to} \quad & x_i \in \{+1,-1\} \end{aligned}\]

zjz 上课的时候没有解释为什么可以这样转换，哥们一边困着一边抄笔记的时候就差点在这里掉线了。意思就是说在 \(i \in S\) 的时候取 \(x_i=1\) 否则为 \(-1\)，这样的话只有在不同集合中的 pair \((i,j)\) 会被计入。注意上下两个形式所考虑的 \((i.j)\) 不同，因此有系数上的轻微差别。

Step 2

自然地会想到取一个 \(n\) 维向量 \(\textbf x = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n\end{bmatrix}\) 使得 \(x_ix_j=X_{ij}\)，其中 \(X=\textbf x \textbf x^T = (X_{ij})\)。因此可以转换为：

\[\begin{aligned} \textbf{maximize} \quad & \frac 1 4 \sum_{i \in V} \sum_{j \in V}w_{ij} (1-X_{ij}) \\ \textbf{subject to} \quad & X=\textbf x \textbf x^T \text{ and }X_{ii}=1 \end{aligned}\]

其中有这就变成了一个纯正的 symmetric & semi-positive definite matrix，看起来已经脱离了 maxcut 问题中的设定。更进一步的话舍弃掉 \(X=\textbf x \textbf x^T\) 这一条件，直接替换为 \(X\) 对称半正定，也即：

\[\begin{aligned} \textbf{maximize} \quad & \frac 1 4 \sum_{i \in V} \sum_{j \in V}w_{ij} (1-X_{ij}) \\ \textbf{subject to} \quad & X \text{ is symmetric and semi-positive definite, with }X_{ii}=1 \end{aligned}\]

就是理想的转换了。

zjz 在课上不是这样直接一步出结果，稍有不同的是他把 \(x_i\) 又进行了一步变换达到 \(\textbf x _i \in \mathbb R^n\)。

Step 3

一个自然的往 LP 转换的想法是把 \(x_ix_j\) 替换为 \(z_e\)，其中 \(e = (i,j) \in E\)，\(z_e=-1\) 表示 \((i,j) \in S \times T\cup T \times S\)，否则 \(z_e=1\)。然后用一些简化将 \(z_e\) 加入 constraints。

\[\begin{aligned} \textbf{maximize} \quad & \frac 1 2 \sum_{e \in E} w_{ij}(1-z_e) \\ \textbf{subject to} \quad & z_{(u,v)} \geq -x_u -x_v -1 \\ &z_{(u,v)} \geq x_u + x_v-1 \\ & x_v \in [-1,1] \end{aligned}\]

实际上 this attempt fails，因为取个 \(x_u=0,x_v=0,z_{(u,v)}=-1\) 也能够满足 constraints，但这没有意义。

Step 4

另一种方法是考虑将每个顶点用一个 \(n\) 维向量表示出来，将 \(x_ix_j\) 替换为 \(\textbf x _i ^T \textbf x_j\)。这样转换的优点在于可以把所有的 \(n\) 维向量放在 \(\mathbb R^n\) 的单位球 \(\mathbb S^{n-1}\) 上，这既出于归一化的考虑，也是因为

\[\frac 1 4 \|\textbf x_u - \textbf x_v\|^2 = \frac 1 2(1-\textbf x_u^T\textbf x_v)\]

这样问题就转换为了

\[\begin{aligned} \textbf{maximize} \quad & \frac 1 2 \sum_{(i,j)\in E}w_{ij} (1-\textbf x_i ^T\textbf x_j) \\ \textbf{subject to} \quad & \textbf x_i \in \mathbb S^{n-1} \text{ for any } i =1,2,\cdots,n \end{aligned}\]

事实上这不是一个等价的转换，某种程度上来说只是单向的。在 maxcut 问题中我们可以对所有 \(i \in S\) 取 \(\textbf x_i =e_1\)，对所有 \(j \in T\) 取 \(\textbf x_j =-e_1\)。但并非上述问题的所有解都可以在 maxcut problem 中找到一个合适的解。我们也把 \(x_i \in \{+1,-1\}\) 这一整数规划的条件舍弃了，改为 \(\textbf x_i \in \mathbb S^{n-1}\)。

称这一问题是 maxcut 问题的 relaxation，顾名思义放松了一些条件。

因此，记 step 4 中问题的 optimal cost 是 \(\mathrm{Maxcut}^0(S)\)，原 maxcut problem 的 optimal cost 记为 \(\mathrm{OPT}(G)\)，于是有

\[\mathrm{Maxcut^0(S)} \geq \mathrm{OPT}(G),\]

也就是说如果找到一个上述问题的 \(\alpha\)-approximation \(W^0(S)\)也就有了原问题的 \(\alpha\)-approximation，这是因为

\[W^0(S) \geq \alpha \ \mathrm{Maxcut^0(S)} \geq \alpha \ \mathrm{OPT}(G).\]

Step 5

通过在上述问题中取 \(X_{ij} = \textbf x_i ^T \textbf x_j\) 可以得到一个新的更抽象化的优化问题：

\[\begin{aligned} \textbf{minimize} \quad & X \cdot A = \sum_{i,j \in V} X_{ij} A_{ij} \\ \textbf{subject to}\quad & X \succeq 0 \\ & X_{ii}=1 \end{aligned}\]

看起来是做了一点 relaxation，我们舍弃了 \(\textbf x_i\) 这些表达，直接用一个模糊的 \(X \succeq 0\) 代替了，实际上它是和 step 4 转化出的问题

相互等价。这是因为：

\[\begin{aligned} X \in \mathbb S_+^n \text{ is feasilble} & \iff X_{ii}=1 \text{ for any }i \in V \\ & \iff \|x_i\|=1 \text{ for any }i \in V \\ & \iff x_i \in \mathbb S^{n-1} \text{ for any }i \in V \end{aligned}\]

至此得到了一个简洁的 symmetric semi-positive definite matrix 问题，这和 step 2 是一致的。

Remark

在 step 2 中已经提到，zjz 在课上不是这样直接一步出结果，稍有不同的是他把 \(x_i\) 又进行了一步变换达到 \(\textbf x _i \in \mathbb R^n\)。

Step 2 和 step 5 转化出的问题在形式上相同是表面上的，实际上他的做法很合理很本质，因为 step 2 中的 symmetric positive definite matrix \(X\) with \(X_{ii}=1\) 可以通过 Cholesky 分解为 \(X =L^TL\)，且有 \(L=\begin{bmatrix} l_1 & l_2 & \cdots & l_n \end{bmatrix}\)，事实上把 \(l_i\) 替换成 \(\textbf x_i\) 就是 step 5 转换出的问题。

（注意到 \(X_{ij} =\textbf x_i ^T \textbf x_j\)，因此 \(X = \begin{bmatrix}\textbf x_1 & \cdots & \textbf x_n \end{bmatrix}^T \begin{bmatrix}\textbf x_1 & \cdots & \textbf x_n\end{bmatrix}\)）

而这一分解是后面得到 \(0.878\)-approximation 的 geometrical foundation，因为这个结论是在 \(\mathbb R^n\) 上通过估算内积得到的。

0.878-approximation

在 maxcut problem 中有一个著名的 \(0.878\)-approximation，也即已经证明了

\[E(W(S)) \geq 0.878 \mathrm \ \mathrm{OPT}(G)\]

~~不详述证明了因为我也不是很会（~~，也不是不会因为写出来其实很简洁，下面给出了证明，但这个东西是我一边写 cheatsheet 一边肝到五点多写完的所以当时是实在没心情了（x

然后讨论一下为什么这个看起来有点怪的 approximation 参数值是重要的，以及回收标题。

Proof

前面已经说明了所有的 \(\textbf x_i\) 都在单位球上，当它们都已知时以下给出一个构造 cut 的手段并计算其期望。

任过单位球作一个割平面 \(\{\textbf u^T \textbf x =0 \mid \textbf x \in \mathbb S^{n-1}\}\)，对于所有 \(\textbf x_i \in \{\textbf u ^Tx >0\} \cap \mathbb S^{n-1}\) 取 \(i\in S\)，其余放入 \(T\)。于是一对 \((i,j) \in S \times T\) 当且仅当割平面穿过 \(\textbf x_i,\textbf x_j\) 的夹角。这一分割得到的 sum of weight 的期望是：

\[E(W(S)) = \sum_{i,j \in V} w_{ij}P((i,j)\in S\times T) = \sum_{i,j \in V}w_{ij} \left(\frac{\arccos \textbf x_i^T \textbf x_j}{\pi}\right)\]

和 symmetric semi-definite matrix 的结果 \(\mathrm{Maxcut} ^0(S) = \frac 1 2 \sum_{i,j \in V} w_{ij}(1-\textbf x_i^T\textbf x_j)\) 相比，考虑函数 \(\arccos x\) 和 \(\frac 1 2(1-x)\) 的最小比值是 \(0.878\)，则有

\[E(W(S)) \geq 0.878 \ \mathrm{Maxcut}^0(S) \geq 0.878 \ \mathrm{OPT}(G).\]

Why is 0.878 important?

首先考虑一个 maxcut problem 的 decision version：对于给定的图 \(G=(V,E)\) 和给定的 \(k>0\)，能否找到一个 sum of weight \(W(S) \geq k\) 的 cut \(S\)？这个问题 NP-complete，只要把所有的 cut 枚举出来然后逐个验证 sum of weight 是否大于等于 \(k\) 即可。

事实上除非 NP = P，否则不可能找出一个 polynomial time solution to maxcut problem，标题回收。

另外除非 NP = P，否则也不可能对任意的 \(\varepsilon <1\) 都可以找到一个 \(\varepsilon\)-approximation algorithm。比较强的结果是 \(\varepsilon > 16/17\) 时 \(\varepsilon\)-approximation algorithm 不存在，而如果 the unique games conjecture is true 则 \(0.878\)-approximation 已经是最佳估计了。

题外话是对于 integer programming 里提到过的 Knapsack problem 是可以找到任意的 \(\varepsilon\)-approximation algorithm 的，这样的问题被称为 admit a PTAS。

SDP Dual

Lagrangian Duality

今天在摸 Lagrangian duality，又回来摸了一下 max cut，玩出来一个好玩的东西然后一查什么嘛果然是早就有的答案（

先把 step 5 得到的 SDP 问题重写一下。原来长这样：

\[\begin{aligned}\textbf{minimize} \quad & X \cdot A = \sum_{i,j \in V} X_{ij} A_{ij} \\ \textbf{subject to}\quad & X \succeq 0 \\ & X_{ii}=1 \end{aligned}\]

主要就是把 \(X_{ii}=1\) 修改成和正定对称阵的内积形式：

\[\begin{aligned}\textbf{minimize} \quad & X \cdot A = \sum_{i,j \in V} X_{ij} A_{ij} \\ \textbf{subject to}\quad & X \succeq 0 \\ & X \cdot (e_ie_i^T)=1 \quad \text{for }\ i=1,2,\cdots, n \end{aligned}\]

写成 Lagrangian 得到 \(L(X,\lambda) = X \cdot A + \sum_{i}^n \lambda_i (X\cdot(e_ie_i^T)-1) = X\cdot(A+\mathrm{diag}(\lambda _1,\cdots,\lambda _n)) -\sum_{i=1}^n \lambda _i\)，其 dual problem 为

\[\begin{aligned} \textbf{minimize} \quad & \sum_{i=1}^n \lambda _i \\ \textbf{subject to} \quad & \mathrm{diag}(\lambda_1,\cdots,\lambda_n) \succeq A \\ & \lambda \succeq 0 \end{aligned}\]

取 \(t =\frac 1 n \sum_{i=1}^n \lambda _i\) 于是有 \(\lambda = t \textbf 1 - u\) 且 \(\textbf 1^T u=0\)。于是问题转化为：

\[\begin{aligned} \textbf{minimize} \quad & nt \\ \textbf{subject to} \quad & tI \succeq A+\mathrm{diag}(u_1,\cdots,u_n) \\ & u^T \textbf 1=0 \end{aligned}\]

Maximum Eigenvalue Programming

考虑一对 primal problem 和 dual problem：

\[\begin{aligned} \textbf{maximum} \quad & A \cdot X \\ \textbf{subject to} \quad & X \cdot I =1 \\& X \succeq 1 \end{aligned} \quad \quad \quad \begin{aligned}\textbf{minimize} \quad & v \\ \textbf{subject to }\quad & vI -A\succeq 0 \\ \\ \end{aligned}\]

右边的显然是特征值问题，optimal solution 和 optimal cost 即为 \(v = \lambda_{max} (A)\)。左边的则与上述问题类似。

Back to Max Cut

因此 max cut problem 可以转化为：

\[\begin{aligned} \textbf{minimize} \quad & n \lambda_{max}(L+\mathrm{diag} (u_1,\cdots,u_n)) \\ \textbf{subject to} \quad & u^T \textbf 1=0 \end{aligned},\]

最终的结论是：

\[\frac n 4 \lambda_{max} (L(G)) \geq \mathrm{Maxcut}^0(S) \geq \mathrm{OPT}(G).\]

其中 \(L(G)\) 是 \(G\) 的 Laplacian matrix。~~这个真不会证~~

『姑妄言之姑妄听之』

请为 max cut problem 找一个 polynomial time solution