动机
独立随机符号以一半概率切开每条边。较好算法应利用哪些顶点对值得分开的信息,又保留足够结构,把信息转成真正的割。单位向量提供中介语言:相反方向强烈要求分离,相同方向不要求,中间角度则表达部分分离。
一个共用随机超平面把所有向量转成符号。各边事件互相关联,但个别概率有简单角度公式。比较此公式与松弛目标,是近似证明的核心。单画向量或求连续规划,都未保证离散割质量;比较论证才补上缺口。
定义
设 G=(V,E) 是有限无自环无向图,有 n≥1 个顶点,边权 wij 非负。割给每顶点符号 si∈{−1,1},权重为
cut(s)={i,j}∈E∑wij21−sisj.以 OPT 表示最大值。向量松弛为每顶点指定单位向量 vi∈Rn,最大化
F(v)={i,j}∈E∑wij21−⟨vi,vj⟩.最大值记为 SDP。每条边只计一次,不按两个方向重复计。
符号解可取 vi=sie1 而成为向量可行解,所以 SDP≥OPT。最大化松弛给上界。单位球面限制在向量坐标中本身不是凸描述;矩阵表述才揭示半正定结构。
实对称矩阵 X 若对所有实向量 a 都有 aTXa≥0,称为半正定,记作 X⪰0。Gram 矩阵的元素为 Xij=⟨vi,vj⟩。松弛等价于
max {i,j}∈E∑wij21−Xij,X⪰0,Xii=1 (i∈V).
Gram 矩阵必半正定,因为其二次型是 ∥i∑aivi∥2。反之,实对称谱定理把半正定矩阵分解为 BBT,以 B 各行作向量即可;对角一使各行为单位向量。谱定理是本篇使用而不重证的线性代数前提。矩阵可行域为凸,因为非负加权平均保持二次型不等式及对角条件。
定理 / 命题
取 g∈Rn,各坐标独立服从标准正态。若 ⟨g,vi⟩≥0,设 si=1,否则 si=−1。对夹角 θ∈[0,π] 的两单位向量,有
Pr(si=sj)=πθ.所以舍入割的期望值为 {i,j}∈E∑wijarccos(⟨vi,vj⟩)/π。
定义
α=0<θ≤πminπ(1−cosθ)2θ.对每个可行向量解,随机超平面舍入满足 E[cut(s)]≥αF(v)。若向量解最优,便得 E[cut(s)]≥αOPT。最小值在唯一满足 tan(θ∗/2)=θ∗ 的 θ∗∈(π/2,π) 取得。
精确常数是上式的最小值,约为 0.878567。严格数值下界 α>0.87856 见 Goemans 与 Williamson 引理 3.5。以下会证微积分刻画;小数下界是引用的数值细化,并非由本篇浮点计算推得。多项式时间半正定求解器及经认证的数值精度实现不在本篇范围。
证明思路或证明
为何正态分布给均匀角度
联合标准正态密度正比于 exp(−∥g∥2/2),正交换坐标不改变它。若 0<θ<π,两向量张成一平面。把 g 投影到该平面的正交坐标,得到旋转对称的二维正态分布。极坐标密度只依赖半径,所以角度在整圈均匀。
投影法向量在两个各宽 θ 的扇形内,会给两向量不同符号。可通过旋转法向量理解:每向量的正半圈长 π,两正半圈的对称差总长为 2θ。除以 2π 即得 θ/π。若 θ=0,向量相同,符号总相同;若 θ=π,向量相反,除了概率零的垂直超平面,符号总不同。两个端点亦符合公式。
每个单位向量的正态内积非退化,所以精确等于零的概率为零。零时任意的符号规则不改变概率;顶点有限,所以任何顶点出现零的概率仍为零。这使用理想连续分布,改成有限精度采样须另控误差。
以 Iij 表示边跨割的指示变量。由割权为 ∑wijIij,期望线性性给出公式。不同边无需独立,一般也不独立,因为同一超平面决定全部符号。这展示相关舍入仍可只靠边际概率精确分析。
概念视角分析
把舍入看成对 Gram 矩阵逐项取反正弦
把舍入后的符号记成随机矩阵 sisj。因为 sisj=1−21[si=sj],跨割概率给出
E[sisj]=1−π2θij=π2arcsin⟨vi,vj⟩,这是由于 arccosx+arcsinx=π/2。因此就期望而言,舍入把 Gram 矩阵 X 换成各项为 π2arcsinXij 的矩阵。以三角形为例,Xij=−1/2 变成 −1/3,与乘积 −1,−1,+1 的平均一致。
从角度转到目标
固定可行向量解 v,对每条边记 θij=arccos⟨vi,vj⟩∈[0,π]。若 θij>0,把 α 作为最小值的定义在 θ=θij 处取值,便得
πθ≥α21−cosθ.θij=0 时两边均为零。把每条边的不等式乘以其权 wij≥0(不等号方向不变)再对边求和。由跨割概率定理及期望线性性,
E[cut(s)]={i,j}∈E∑wijπθij≥α{i,j}∈E∑wij21−⟨vi,vj⟩=αF(v).对最优松弛,F(v)=SDP≥OPT,所以 E[cut(s)]≥αOPT。
证明透视
每一步用到哪个假设
这个证明由四步组成,每步用掉不同的假设。第一,跨割概率 θij/π 是等式,舍入在此没有损失。它只需要超平面的高斯(Gauss)对称性及每对顶点的边际分布,完全不需要不同边之间独立。第二,所示的单变量不等式是唯一有损失的一步,也是 α 唯一出现之处。它逐边成立,所以可同时用于每个边角度。它只在角度 θ∗ 处取等:当 θ=π 时,比值 2θ/[π(1−cosθ)] 等于 1,所以两向量相反的边没有损失。
第三,求和需要 wij≥0。取一条权为 −1、两向量相反的边:此时 E[cut(s)]=−1、F(v)=−1,但 αF(v)≈−0.8786>−1,所声称的不等式不成立。第四,过渡到 OPT 用到 v 是最优松弛解,即 F(v)=SDP,以及由嵌入符号解得到的 SDP≥OPT。若去掉最优性,只剩下 E[cut(s)]≥αF(v)。
保证有两个来源不同的比较:几何把舍入期望与提供的向量值比较;松弛把其最优向量值与整数最优比较。若随便提供差的可行向量,只能使用第一个。这可防止把可行性混作近乎最优性。
找出精确的单变量最小值
令 h(θ)=2θ/[π(1−cosθ)]。当 θ↓0,由 1−cosθ∼θ2/2,h(θ)→∞。导数符号等于
N(θ)=1−cosθ−θsinθ,N′(θ)=−θcosθ
的符号。由 N(0)=0 开始,此函数在 (0,π/2) 严格下降,在 (π/2,π) 严格上升。又 N(π/2)=1−π/2<0,N(π)=2>0。连续性及严格单调性给后一区间唯一零点 θ∗。所以 h 在此之前递减、之后递增,证明最小值刻画。
方程 N(θ∗)=0 即 1−cosθ∗=θ∗sinθ∗。由半角公式及 0<θ∗/2<π/2,得到 tan(θ∗/2)=θ∗,也得 α=(θ∗+1/θ∗)/π。证明使用这些精确等式,而非四舍五入小数。作为较弱的初等检查,[0,π] 上 θ≥1−cosθ,因差的导数 1−sinθ≥0;因此 α≥2/π>0。
近似最优化及实际承诺
矩阵可行域闭且有界:由 Gram 表述或二阶二次型,半正定及对角一蕴含 ∣Xij∣≤1。它非空,例如单位矩阵可行。连续线性目标因此取得最大值;此存在性论证却未给有限精确求最大值算法。
若求解器提供真正可行的向量,满足 F(v)≥SDP−η、η≥0,同一证明给
E[cut(s)]≥α(SDP−η)≥αOPT−αη.
这是加性误差陈述。若 OPT>0,要把比率损失限制于 ε,需 η≤εOPT/α,或用可实际取得的最优值下界保证此式。只报很小数值残差,不能证明可行性或目标条件。近乎半正定矩阵须先有理由地修补,才可用精确向量定理。
期望保证也不是每次采样的保证。设舍入值为 Z,则 0≤Z≤OPT。当 0<ε<α、OPT>0,令 p=Pr[Z≥(α−ε)OPT],并假设 EZ≥αOPT。把成功值上界为 OPT,其余上界为门槛,可得
p≥1−α+εε.
独立重复 r 次并保留最好观察割,失败概率至多 (1−p0)r,其中 p0 是上面的下界。算法保留最好输出不需要知道最优值,门槛只用于分析。若权重全零,所有割均最优,无需作这种含除法的讨论。
证明透视
近似比来自哪里
证明有三座桥:整数符号解给可行 Gram 矩阵;边角度决定超平面分离概率;单变量不等式比较该概率与边的松弛贡献。最后相加需要非负权。把桥分开,可看出未优化向量、改变舍入或容许负权时,究竟哪个结论失效。
例题详解
一条权重 w≥0 的边,取 v1=−v2。角度为 π,松弛贡献为 w,每个非垂直超平面都分开两者。因此舍入以概率一得到权重 w。本例因子为一,优于最坏常数;普遍下界不必在每个输入达到。
无权三角形取平面单位向量角度零、2π/3、4π/3。每对内积 −1/2,故 F=3(3/4)=9/4。每边以 2/3 概率跨割,期望为二,亦为整数最优。边事件相关:除了零概率边界,恰有两边跨割。分数目标 9/4 并未宣称存在该不可能值的割。
两边路径 1−2−3 的权重为二、三。取 v1=(1,0)、v2=(1/2,3/2)、v3=(−1,0),边角为 π/3,2π/3,期望割权 2/3+2=8/3。向量目标为 2(1−1/2)/2+3(1+1/2)/2=11/4。整数最优为五,把顶点二与两端分开即可。这些向量可行却不最优,所以定理比较 8/3 与 α(11/4),不能自动与 α⋅5 比较。
反例模式
可行向量本身未必近似最优
错误命题:每个可行向量解经随机超平面舍入,所得割的期望权至少为 αOPT。取一条权为 3 的边,并令两个单位向量相同,v1=v2=e1。Gram 矩阵 (1111) 半正定且对角为一,所以可行。角度为 0,故 F(v)=3(1−1)/2=0,两点永不被分开,舍入割权为 0。然而 OPT=3,αOPT≈2.636。这并不违反定理,因为定理只保证 E[cut(s)]≥αF(v)=0。修正方法是提供最优或可证近乎最优的松弛解:取 v2=−v1 时,向量目标为 3,舍入割权以概率一等于 3。舍入质量与最优化质量是两个不同要求。
常见错误
常见错误
(半正定不等于元素非负,跨边事件也不独立)
半正定不表示每个元素非负,三角形使用负的非对角元素。向量目标也不是真正可行离散割。超平面为全部顶点共用,不能把跨边概率当作互相独立而相乘。
α 的小数近似不是精确定理常数。精确最小值、已严证下界及求解器容差各有不同角色。数值最优化及采样可逼近理想算法,但误差须连到明述的加性或乘性保证,不能藏在实现措辞内。
总结
Gram 矩阵把符号乘积凸化,保留每个真正割。旋转对称性给精确角度分离概率,单变量比较产生期望近似因子。最小值及唯一驻点角度均已严格刻画,而优化后向量、非负权及受控数值误差仍是明确要求。
练习
快速检查
(直接证 Gram 矩阵半正定,并解释单位向量为何给对角一。)
解答 · 答案
任意实系数 ai 满足 aTXa=i,j∑aiaj⟨vi,vj⟩=∥i∑aivi∥2≥0;又 Xii=∥vi∥2=1。无需假设各元素为正,即证两个约束。
快速检查
(两个正交单位向量的一条权四边,求松弛贡献及分离概率。)
解答 · 答案
角度 π/2、内积零。松弛贡献 4/2=2,分离概率 1/2,期望割贡献也为二。概率与加权贡献的单位不同,不应混同。
快速检查
(证明三角形向量最优恰为 9/4,而不只是提供一个可行值。)
解答 · 答案
任意三单位向量有 0≤∥v1+v2+v3∥2=3+2i<j∑⟨vi,vj⟩,故内积总和至少 −3/2,目标至多 3/2−21(−3/2)=9/4。前述等距向量达到此值。整数最优二,故也证明三角形的精确松弛落差。
快速检查
(精确期望保证及正最优下,取 ε=α/2,给取得至少最优 α/2 倍的正概率下界,及独立重复后失败界。)
解答 · 答案
一般界给 p0=(α/2)/(1−α/2)>0。取 r 个独立超平面的最好者,失败概率至多 (1−p0)r。乘积界需要各次重复独立;单次期望证明却不要求各边独立。