動機
獨立隨機符號以一半概率切開每條邊。較好算法應利用哪些頂點對值得分開的資訊,又保留足夠結構,把資訊轉成真正的割。單位向量提供中介語言:相反方向強烈要求分離,相同方向不要求,中間角度則表達部分分離。
一個共用隨機超平面把所有向量轉成符號。各邊事件互相關聯,但個別概率有簡單角度公式。比較此公式與鬆弛目標,是近似證明的核心。單畫向量或求連續規劃,都未保證離散割品質;比較論證才補上缺口。
定義
設 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。乘積界需要各次重複獨立;單次期望證明卻不要求各邊獨立。