求解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é)論:

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

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

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

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

簡單地說就是對于不在凸集中的點(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乡翅。

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

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末尚洽,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子靶累,更是在濱河造成了極大的恐慌腺毫,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件挣柬,死亡現(xiàn)場離奇詭異潮酒,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)邪蛔,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進(jìn)店門急黎,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人侧到,你說我怎么就攤上這事勃教。” “怎么了匠抗?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵故源,是天一觀的道長。 經(jīng)常有香客問我汞贸,道長绳军,這世上最難降的妖魔是什么印机? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮删铃,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘踏堡。我一直安慰自己猎唁,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布顷蟆。 她就那樣靜靜地躺著诫隅,像睡著了一般。 火紅的嫁衣襯著肌膚如雪帐偎。 梳的紋絲不亂的頭發(fā)上逐纬,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天,我揣著相機(jī)與錄音削樊,去河邊找鬼豁生。 笑死,一個(gè)胖子當(dāng)著我的面吹牛漫贞,可吹牛的內(nèi)容都是我干的甸箱。 我是一名探鬼主播,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼迅脐,長吁一口氣:“原來是場噩夢啊……” “哼芍殖!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起谴蔑,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤豌骏,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后隐锭,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體窃躲,經(jīng)...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年钦睡,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了框舔。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,872評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡赎婚,死狀恐怖刘绣,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情挣输,我是刑警寧澤纬凤,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站撩嚼,受9級特大地震影響停士,放射性物質(zhì)發(fā)生泄漏挖帘。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一恋技、第九天 我趴在偏房一處隱蔽的房頂上張望拇舀。 院中可真熱鬧,春花似錦蜻底、人聲如沸骄崩。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽要拂。三九已至,卻和暖如春站楚,著一層夾襖步出監(jiān)牢的瞬間脱惰,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工窿春, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留拉一,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓旧乞,卻偏偏與公主長得像舅踪,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個(gè)殘疾皇子良蛮,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評論 2 361