Semidefinite Programs

LP for Max-Cut

$\begin{aligned} \text{max}&&&\sum_{uv\in E}y_{uv}\\ \text{s.t} &&&y_{uv}\le |x_u-x_v| && \forall uv\in E\\ &&& x_v\in \{0,1\} &&\forall v\in V \end{aligned}$

有绝对值, 非线性规划, 转化为下面的形式:

$\begin{aligned} \text{max}&&&\sum_{uv\in E}y_{uv}\\ \text{s.t} &&&y_{uv}\le y_{uw}+y_{wv} && \forall u,v,w\in V\\ &&&y_{uv}+ y_{uw}+y_{wv}\le 2 && \forall u,v,w\in V\\ &&& y_{uv}\in \{0,1\} &&\forall u,v\in V \end{aligned}$

也就是$\forall u,v,w\in V$, $\{u,v\}$, $\{u,w\}$, $\{v,w\}$中有0或2对是交错的.
integrality gap: $\ge 2$
也可以写成二次规划:

$\begin{aligned} \text{max}&&&\sum_{uv\in E}y_{uv}\\ \text{s.t} &&&y_{uv}\le \frac{1}{2}(1-x_ux_v) && \forall uv\in E\\ &&& x_v\in \{-1,1\} &&\forall v\in V \end{aligned}$

即

$\begin{aligned} \text{max}&&&\sum_{uv\in E}\frac{1}{2}(1-x_ux_v)\\ \text{s.t} &&& x_v^2=1 &&\forall v\in V \end{aligned}$

松弛成向量规划

$\begin{aligned} \text{max}&&&\frac{1}{2}\sum_{uv\in E}(1-\langle x_u,x_v\rangle)\\ \text{s.t} &&& \langle x_v,x_v\rangle=1 &&\forall v\in V\\ &&& x_v\in \mathbb R^n \end{aligned}$

半正定规划SDP

定义: 对称矩阵$A\in \mathbb R^{n\times n}$是半正定的当且仅当对于任意$x\in \mathbb R^n$, $x^T Ax\ge 0$, 记做$A \succcurlyeq 0$
定理: 对于对称阵$A\in \mathbb R^{n\times n}$:

$A \succcurlyeq 0 $ 当且仅当所有特征值$\lambda(A)\ge 0$ 当且仅当存在$B\in \mathbb R^{n\times n}, A=B^TB$

半正定规划:
$C,A_1,\cdots,A_k\in \mathbb R^{n\times n}, b_1.b_2,\cdots,b_k\in \mathbb R$

$\begin{aligned} \text{max}&&& tr(C^TY)=\sum_{i=1}^n\sum_{j=1}^nc_{ij}y_{ij}\\ \text{s.t} &&& tr(A_r^T Y)\le b_r && \forall 1\le r\le k\\ &&& Y \succcurlyeq 0\\ &&& \text{symmetric } Y\in R^{n\times n} \end{aligned}$

等价形式:

$\begin{aligned} \text{max}&&& tr(C^TY)=\sum_{i=1}^n\sum_{j=1}^nc_{ij}\langle v_i,v_j\rangle\\ \text{s.t} &&& \sum_{i=1}^n\sum_{j=1}^na_{ij}^{(r)}\langle v_i,v_j\rangle\le b_r && \forall 1\le r\le k\\ &&& v_1,\cdots,v_n\in R^{n} \end{aligned}$

SDP是LP的推广
SDP是半正定规划的一类
可以可以被 ellipsoid method高效解答
- 在$poly(n, 1/\epsilon)$时间内得到$OPT \pm\epsilon$

舍入(Rounding)

对于最大割问题, 假设松弛到的SDP的解为$x_v^*$, 舍入到原问题解$\hat x_v$:

均匀随机选取一个单位向量$u\in \mathbb R^n$, $\Vert u \Vert_2=1$
则$\hat x_v=sgn (\langle x_v^,u\rangle)$. (注意这里的$x_v^$已经转化为了n维向量了)
几何理解: SDP的解是球内的点, 随机找一个超平面, 将球分成两半, 分别对应原问题解1和-1.
生成均匀随机单位向量的方法:
- 随机选取$r=(r_1,\cdots,r_n)\in \mathbb R^n$, 每个$r_i\sim N(0,1)$, 独立同分布的高斯分布
- 然后归一化$u=\frac{r}{\Vert r\Vert_2}$就是均匀随机的单位向量
- 原因:
  - $\Pr[(r_1,\cdots,r_n)]=\prod _{i=1}^n\frac{1}{\sqrt{2\pi}}e^{-r_i^2/2}=(2\pi)^{-d/2}e^{-\Vert r\Vert^2/2}$
  - 是球面对称的, 之和离球心距离相关
- 本问题中不用归一化(不影响符号)

近似比分析:

$\begin{aligned} \mathbb E[\text{cut}]&=\sum_{uv\in E}\Pr[\text{sgn}(\langle x_u^*,r\rangle)\ne \text{sgn}(\langle x_v^*,r\rangle)]\\ &=\sum_{uv\in E}\frac{\theta _{uv}}{\pi}\\ &=\sum_{uv\in E}\frac{\arccos \langle x_u^*,x_v^*\rangle}{\pi}\\ &\ge 0.878\cdot \frac{1}{2}(1-\langle x_u^*,x_v^*\rangle) \end{aligned}$

其中$\theta_{uv}=\angle x_u^ox_v^$, 使用$\Vert x_u^\Vert\cdot \Vert x_v^\Vert \cos\theta_{uv}=\langle x_u^,x_v^\rangle$, 得$\cos\theta_{uv}=\langle x_u^,x_v^\rangle$
$0.878$是通过极限算出来的.
所以近似比为$0.878$.

Unique Games Conjecture

没看懂, 算了吧.

Constraint Satisfaction Problem

变量: $X=\{x_1,x_2,\cdots,x_n\}$
域: $\Omega$, 通常$\Omega=[q]$, $q$有限
限制: $c=(\psi, S)$, 其中$\psi:\Omega^k\to\{0,1\}$, 范围$S\subseteq X$是一个$k$元子集.
CSP实例: 一个定义在$X$上的限制集
赋值: $\sigma\in\Omega ^X$ 对于每个变量赋值
如果$\psi(\sigma_s)=1$, 限制$c=(\psi,S)$被满足
例子:
- 最大割: $q=2$, 限制为不等于.
- $k$-SAT: $q=2$, 限制是$k$-从句
- 匹配/覆盖: $q=2$, 限制为$\sum\le 1$(或$\sum\ge 1$).
- $k$着色: $q=k$, 限制为不等于
- 图同构: 限制为邻接矩阵
- unique games: $\Omega=[q]$, 每个限制是任意的二元双射谓词: $\psi: \Omega^2\to \{0,1\}$, 其中$\forall a\in\Omega$, 存在唯一的$b\in \Omega$, $\psi(a,b)=1$.
CSP算法问题: 给定CSP实例$I$
- 满足性: 是否存在一个赋值满足所有的限制
  - 搜索: 找到满足的赋值
- 优化: 找到赋值满足尽可能多的限制.
  - 驳斥(对偶): 证明不存在满足$>m$个限制的赋值, $m$尽量小
- 计数: 估计满足限制的赋值的数量
  - 采样: 随机采样一个满足赋值
  - 推断: 观察一个满足的赋值, 猜测未知变量的值
各CSP问题难度见ppt