照例先引用兩篇文章:
第一篇關(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
中的超平面(Hyperplane)定義為集合
岭参。其中
,
尝艘。
- 這里書上定義一寫錯(cuò)了演侯,但是不妨礙理解。類比低維空間的直線和平面方程即可背亥。
- 由于
不一定等于0秒际,因此超平面不一定過原點(diǎn)。
-
中的超平面為一
維流形狡汉。(這個(gè)性質(zhì)可能跟我們要討論的問題沒什么關(guān)系)
- “超”的意思是“在維度上做推廣”娄徊。由于當(dāng)
時(shí)我們稱定義1中所說的這種集合為“平面”,所以推廣地說對于任意
盾戴,上邊定義的集合就叫超平面寄锐。注意,
中的直線也是超平面尖啡。
定義2
中的凸體(Convex body)定義為有界閉凸集橄仆。
凸集的定義和數(shù)學(xué)中是一樣的。下面舉幾個(gè)例子:
-
線性規(guī)劃問題的每一個(gè)限制條件(包括符號限制)都定義了一個(gè)超平面和兩個(gè)半空間(Half-space)可婶。半空間就是將
用一個(gè)超平面一分為二所得到的集合沿癞。顯然兩個(gè)半空間以對應(yīng)超平面為分界面援雇。當(dāng)限制條件分別為
矛渴,
和=時(shí), 該限制條件對應(yīng)的解空間為一個(gè)半空間(閉的)或超平面。
- 邊長為
的超立方體(Hypercube):
顯然為凸體具温。
- 一個(gè)橢球體(定軸的)為:
蚕涤。在本文中我們可以類比三維地考慮橢球體的集合意義。
-
是一個(gè)平凡的凸集铣猩,但不是凸體揖铜。
下面是與橢圓算法相關(guān)的幾個(gè)比較重要的結(jié)論:
- 解空間為半空間的交。滿足一則限制條件的點(diǎn)集為半空間(或超平面达皿。書上沒有考慮等號限制條件天吓,但是讀者要意識到這一點(diǎn)即可。)峦椰,故滿足所有限制條件的點(diǎn)集為這些半空間的交龄寞。
- 有限個(gè)半空間的交為凸集。因?yàn)橥辜挠邢藿蝗匀皇峭辜?/li>
- 對于一個(gè)凸集
與凸集外一點(diǎn)
汤功,存在超平面使得凸集與該點(diǎn)分居兩側(cè)物邑。文章中是這樣寫的,但這樣寫顯然是錯(cuò)的滔金。二維歐式空間中的開單位圓盤與單位圓上任意一點(diǎn)構(gòu)成反例色解。此性質(zhì)要求凸集是閉的。
證明 考慮
到
的距離餐茵,由于距離函數(shù)是連續(xù)的且在
中可以取下屆科阎,故存在下確界。因此取一列
中的點(diǎn)使得與
的距離趨于下確界忿族,由
是閉集可知下確界可以取到萧恕,且不為0(否則與
在
外矛盾)。之后取中點(diǎn)構(gòu)造垂直超平面即可肠阱。
這就引入了一種名為Separating Oracle的操作:
對于一個(gè)給定的點(diǎn)
票唆,其關(guān)于一個(gè)凸集
的Separating Oracle操作為:要么說明
(返回"YES"),要么返回"NO"加上一個(gè)分割
與
的超平面屹徘。
簡單地說就是對于不在凸集中的點(diǎn)走趋,找個(gè)超平面“切一刀”,把點(diǎn)和凸集分開噪伊。注意簿煌,“找一個(gè)超平面將該點(diǎn)和該凸集分開”與“找一個(gè)半空間覆蓋住原來的凸集”是等價(jià)的。另一方面鉴吹,這樣的超平面的存在性已在上邊有過證明姨伟。
算法
此算法分兩部分理解。第一部分較為簡單豆励,即用二分法逼近最大值夺荒。第二部分用一種很巧妙的方法證明可解性(可解性用來判斷二分法下一步往那邊走)瞒渠,是本算法的關(guān)鍵。
第一部分:二分法
首先技扼,我們使用二分搜索將求解最大值的過程轉(zhuǎn)化為尋找可行解的過程伍玖。考慮
不妨設(shè)最大值存在剿吻,記之為窍箍。當(dāng)
對于任意一個(gè)合適的初始椰棘,若上圖中方程有解則考慮:若此時(shí)方程無解則最大值落在中。其他情況同理榄笙。
對于任意的誤差晰搀,此方法(只考慮二分)的復(fù)雜度都為與矩陣大小無關(guān)的常數(shù)。
第二部分:判斷可解性
對于一個(gè)給定的办斑,現(xiàn)在只須判斷上圖中方程是否有解則可進(jìn)行下一步外恕。首先由之前的敘述可知可行域是一個(gè)凸集,記之為
乡翅。
剩下好難鳞疲,自己也沒懂,不寫了蠕蚜。