單純型算法的復(fù)雜性及改進(jìn)途經(jīng)-資料下載頁(yè)
2025-07-18 13:53本頁(yè)面
【正文】 in?. 0 ,TTnC D X Ye D X YA D X Y Y? ? ?? ?Y用逆變換得到新的內(nèi)點(diǎn) 如何得到 ？ 變換后的近似問題 ? ?? ??m in?s . t. 0 ,TnC D X YA D X Y Y? ? ?已知： 1） 是可行解 1en是 的內(nèi)點(diǎn)， 1|| ||dern d?? n? , 0 1ndR ?? ? ? ?? ?? ?? ?1?1?11? ? ?, 0 01?X TD X enX T e A X A D X enne D X en? ??? ? ? ? ?????2） 將目標(biāo)函數(shù)下降方向 投影到等式約束的零空間得到可行下降方向 ，再用 2）的公式得到新內(nèi)點(diǎn) ? ??D X C??Yd ?Y向等式約束 的零空間投影的公式 ? ?? 0 , 1TA D X X e X??? ??D X C?記 ? ??TA D XBe???????? ?? ? ? ?1 ?TTd I B B B B D X C?? ? ?B在 的零空間投影為 行滿秩 A? ??DX 可逆方陣 ? ?? 0A D X e ?? 行滿秩 B0Bd ?容易驗(yàn)證 ，所以 ? ?? 0 , 0TA D X d e d??？ 任取 ，令 ， 是 的內(nèi)點(diǎn) 1?|| ||dY e rn d???01???? ? ? ? 11? ? ? ?0 , 1TTA D X Y A D X e e Y e enn? ? ? ?? ? ? ?? ? ? ?? ? ? ?所以 是變換后問題的可行內(nèi)點(diǎn) ? ?? 0 , 0TA D X d e d???Y再利用 可得 n??Y又因?yàn)? ? ? ? ? ? ?? ?? ? ? ?211? ? ? ?|| ||?|| ||T T TTTrC D X Y C D X e C D X dn drI B B B B D X Cd?? ????? ????? ? ?所以 ? ? ? ? 1? ? ?TTC D X Y C D X en??? ????（近似目標(biāo)有改進(jìn)） ?X ? ??TA D XBe???????? ?? ? ? ?1 ?TTd I B B B B D X C?? ? ?1?|| ||dY e rn d???????? ?? ?? ??? ?TD X YXe D X Y? ?Karmarkar算法一步迭代公式 Karmarkar算法的收斂性與復(fù)雜性 定理：用 表示初始可行內(nèi)點(diǎn)，用 表示第 次迭代 后得到的可行內(nèi)點(diǎn)，如果取 ，則成立 0X13? ?kkX0e x p 5TkTCX kC X n????????取 ，規(guī)定算法終止條件為 02 LTCX? ?? T kCX ??只要 ，就成立 5k nL?? ?0 0 0e x p e x p 25T T T L Tk kC X C X L C X C Xn ?????? ? ? ? ?????每步迭代計(jì)算復(fù)雜性為 ，所以 Karmarkar算法 的復(fù)雜性為 （可降至 ） ? ?3On? ?4O n L ? ? n L如何將標(biāo)準(zhǔn)線性規(guī)劃問題轉(zhuǎn)化為 Karmarkar標(biāo)準(zhǔn)型？ 0AX bX???110 , 0TnnAX be X x QXx???????Q?（ 充分大） 21212120010 , 0 , 0nTnnTnnnnA X b xe X x Q xe X x x QX x x?????????? ? ?? ? ? ?? ? ?（中間兩約束保證 ） 2 1nx ? ?再令 就得到 Karmarkar標(biāo)準(zhǔn)型 ? ?1,iix Q y i? ? ?如何獲得初始可行內(nèi)點(diǎn)？ m in. 010TTnCXAXeXX????1111m i n . 010 , 0TnnnTnnnC X M xAX Ae xe X xXx???????????（ 充分大） M其中 表示 個(gè) 1組成的向量 nne容易驗(yàn)證， 是右邊問題的可行解 111 nen ??如何滿足最優(yōu)目標(biāo)值等于零的要求？ 用 表示 Karmarkar標(biāo)準(zhǔn)型最優(yōu)目標(biāo)值（未知），選一 *z0? Tz C X?第 次迭代開始時(shí) ，得 k ? Tkz C X??0 ????11|| ||kkkdY e rn d?? ??如果 ，令 ，繼續(xù)迭代 ? ?11? kT Xkz C T Y? ?? ? ?111kk X kX T Y????否則，存在 使 ? ?11 1 1 11? ? ? ?? ?,|| || k Tkk k X k kkdY e r X T Y C X zn d? ?? ? ? ?? ? ? ?個(gè) 作為其估計(jì)值，將目標(biāo)函數(shù)變?yōu)? 此時(shí)減小 ，然后從 繼續(xù)迭代 ?z1?kX ??TC X z?如何滿足最優(yōu)目標(biāo)值等于零的要求？（繼續(xù)） 另一方面，如果某次迭代后目標(biāo)函數(shù)下降不夠預(yù)期值， 例如，不滿足 0e x p 5TkTCX kC X n????????說明 ，此時(shí)可提高 值 *?zz? ?z此外，還有利用對(duì)偶變量的信息解決該問題的方法 課后作業(yè) 1）證明 Karmarkar算法中的 ? ?11rnn??2）用 Karmarkar算法求解下述問題，進(jìn)行兩步 迭代，列出所有中間結(jié)果 1231 2 3m in 1. 010 , 1 , 2 , 3ixxxx x xxi????? ? ???
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1