求解LP問題 | 一種多項(xiàng)式復(fù)雜度的解法：橢圓算法

照例先引用兩篇文章：
第一篇關(guān)于橢圓算法的思路與簡單步驟：The Ellipsoid Algorithm for Linear Programming
第二篇關(guān)于此算法中重要的一個(gè)步驟：Separation Oracles

相比單純性算法剩檀，此算法巧妙的地方在于其控制了復(fù)雜度鹰晨。雖然實(shí)際操作中可能沒有單純形好用，但是它提供了一種LP問題的多項(xiàng)式復(fù)雜度解法，借此可以引出更多更簡單的多項(xiàng)式復(fù)雜度解。因此學(xué)習(xí)的時(shí)候要注意理論推導(dǎo)。建議學(xué)習(xí)時(shí)間為1小時(shí)。

基本定義與概念，

定義1 $R^{n}$ 中的超平面(Hyperplane)定義為集合 $H = \{x|a^{T}x=b\}$ 岭参。其中 $a,x\in R^{n}$ ， $b\in R$ 尝艘。

這里書上定義一寫錯(cuò)了演侯，但是不妨礙理解。類比低維空間的直線和平面方程即可背亥。
由于 $b$ 不一定等于0秒际，因此超平面不一定過原點(diǎn)。
$R^{n}$ 中的超平面為一 $n-1$ 維流形狡汉。（這個(gè)性質(zhì)可能跟我們要討論的問題沒什么關(guān)系）
“超”的意思是“在維度上做推廣”娄徊。由于當(dāng) $n=3$ 時(shí)我們稱定義1中所說的這種集合為“平面”，所以推廣地說對于任意 $n \neq 3$ 盾戴，上邊定義的集合就叫超平面寄锐。注意， $R^{2}$ 中的直線也是超平面尖啡。

定義2 $R^{n}$ 中的凸體(Convex body)定義為有界閉凸集橄仆。

凸集的定義和數(shù)學(xué)中是一樣的。下面舉幾個(gè)例子：

線性規(guī)劃問題的每一個(gè)限制條件（包括符號限制）都定義了一個(gè)超平面和兩個(gè)半空間(Half-space)可婶。半空間就是將 $R^{n}$ 用一個(gè)超平面一分為二所得到的集合沿癞。顯然兩個(gè)半空間以對應(yīng)超平面為分界面援雇。當(dāng)限制條件分別為 $\leq$ 矛渴， $\geq$ 和=時(shí)，該限制條件對應(yīng)的解空間為一個(gè)半空間（閉的）或超平面。
邊長為 $l$ 的超立方體(Hypercube)： $B=\{x|0 \leq x_{i} \leq l , 1\leq i \leq n \}$ 顯然為凸體具温。
一個(gè)橢球體（定軸的）為： $E = \{x| \sum^{n}_{i=1}\frac{x_{i}^{2}}{a^{2}_{i}}\leq 1 \}$ 蚕涤。在本文中我們可以類比三維地考慮橢球體的集合意義。
$R^{n}$ 是一個(gè)平凡的凸集铣猩，但不是凸體揖铜。

下面是與橢圓算法相關(guān)的幾個(gè)比較重要的結(jié)論：

解空間為半空間的交。滿足一則限制條件的點(diǎn)集為半空間（或超平面达皿。書上沒有考慮等號限制條件天吓，但是讀者要意識到這一點(diǎn)即可。）峦椰，故滿足所有限制條件的點(diǎn)集為這些半空間的交龄寞。
有限個(gè)半空間的交為凸集。因?yàn)橥辜挠邢藿蝗匀皇峭辜?/li>
對于一個(gè)凸集 $K$ 與凸集外一點(diǎn) $x$ 汤功，存在超平面使得凸集與該點(diǎn)分居兩側(cè)物邑。文章中是這樣寫的，但這樣寫顯然是錯(cuò)的滔金。二維歐式空間中的開單位圓盤與單位圓上任意一點(diǎn)構(gòu)成反例色解。此性質(zhì)要求凸集是閉的。

證明考慮 $x$ 到 $K$ 的距離餐茵，由于距離函數(shù)是連續(xù)的且在 $K$ 中可以取下屆科阎，故存在下確界。因此取一列 $K$ 中的點(diǎn)使得與 $x$ 的距離趨于下確界忿族，由 $K$ 是閉集可知下確界可以取到萧恕，且不為0（否則與 $x$ 在 $K$ 外矛盾）。之后取中點(diǎn)構(gòu)造垂直超平面即可肠阱。

這就引入了一種名為Separating Oracle的操作：

對于一個(gè)給定的點(diǎn) $x$ 票唆，其關(guān)于一個(gè)凸集 $K$ 的Separating Oracle操作為：要么說明 $x \in K$ （返回"YES"），要么返回"NO"加上一個(gè)分割 $x$ 與 $K$ 的超平面屹徘。

簡單地說就是對于不在凸集中的點(diǎn)走趋，找個(gè)超平面“切一刀”，把點(diǎn)和凸集分開噪伊。注意簿煌，“找一個(gè)超平面將該點(diǎn)和該凸集分開”與“找一個(gè)半空間覆蓋住原來的凸集”是等價(jià)的。另一方面鉴吹，這樣的超平面的存在性已在上邊有過證明姨伟。

算法

此算法分兩部分理解。第一部分較為簡單豆励，即用二分法逼近最大值夺荒。第二部分用一種很巧妙的方法證明可解性（可解性用來判斷二分法下一步往那邊走）瞒渠，是本算法的關(guān)鍵。

第一部分：二分法

首先技扼，我們使用二分搜索將求解最大值的過程轉(zhuǎn)化為尋找可行解的過程伍玖。考慮

求最大值的近似解

不妨設(shè)最大值存在剿吻，記之為窍箍。當(dāng) $c_{0} > M$ 時(shí)上圖方程（相當(dāng)于比原LP問題多了一個(gè)限制條件的新LP問題）沒有可行解。當(dāng)時(shí)有可行解丽旅。
對于任意一個(gè)合適的初始椰棘，若上圖中方程有解則考慮：若此時(shí)方程無解則最大值落在中。其他情況同理榄笙。
對于任意的誤差晰搀，此方法（只考慮二分）的復(fù)雜度都為與矩陣大小無關(guān)的常數(shù)。

第二部分：判斷可解性

對于一個(gè)給定的 $c_{0}$ 办斑，現(xiàn)在只須判斷上圖中方程是否有解則可進(jìn)行下一步外恕。首先由之前的敘述可知可行域是一個(gè)凸集，記之為 $S$ 乡翅。

剩下好難鳞疲，自己也沒懂，不寫了蠕蚜。