半正定規劃、最大割的0.878-近似
優化課上學到了一個非常有意思的例子，學期末疲於奔命之餘做個筆記。
眾所周知，求無向圖的全局最大割是 的：對於無向帶權圖
，求
，最大化所有滿足
的邊權之和。
許多OI選手也許知道，我們很容易得到最大割的0.5-近似：只需要以1/2的概率對每個頂點隨機採樣得到 ，顯然有
。所以有
，故一定存在一種割的方案，大於等於
。
怎麼做得更好？直接的想法是使用整數線性規劃：定義變數 。求解
意義是很顯然的。然後，我們把它作為一個普通的線性規劃來求解。
然而，這不是一個好的鬆弛方法。注意到令 ，那麼就得到了一個所有
的平凡解。
事實上，使用半正定規劃，可以得到一個更優秀的近似。半正定規劃是指有如下形式的問題：
其中 為矩陣內積，即
。
指
半正定。
不難發現這個問題的可行集是一個凸集，故半正定規劃是凸優化的一個特例，可以多項式時間求解。
想法是這樣的：我們把
於是問題轉變為：
其中 是
的Gram矩陣，即
。我們有約束
是因為所有向量都是單位向量。係數為
是因為矩陣中
和
會算兩次。
很容易發現 是半正定矩陣，設
，則
。
現在我們作一次鬆弛，移除Gram矩陣的要求，只要求 是半正定矩陣，即：
這是一個典型的半正定規劃問題。求出 之後我們可以直接使用喬萊斯基分解
得到
。
現在我們來考慮這個演算法的近似效果。與0.5-近似的方法相同，我們通過一個期望的方法證明近似比。這個方法被稱為Goemans-Williamson randomized rounding。
我們現在把每個頂點對應到了單位球上的向量 ，最自然的想法是，我們用一個過原點的超平面把單位球切成兩部分，那麼自然得到了一個割。於是我們隨機取一個單位向量
，若
，則
；若
，則
。
現在我們來考慮這個割的期望：
考慮 張成的平面，兩個向量被割開，當且僅當平面穿過兩個向量的夾角。故
。
現在我們要比較期望結果 與半正定規劃得到的解
。
作出 與
的圖像：
求出兩個函數比值的最小值：
因此，我們得到 。因此，一定存在一個割，至少是最大割的0.878-近似。
事實上，這已經是一個很好的近似了，因為有定理：
最大割的k-近似在 時是
的。
推薦閱讀：
