【正文】 n?. 0 ,TTnC D X Ye D X YA D X Y Y? ? ?? ?Y用逆變換得到新的內點 如何得到 ？ 變換后的近似問題 ? ?? ??m in?s . t. 0 ,TnC D X YA D X Y Y? ? ?已知： 1） 是可行解 1en是 的內點， 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） 將目標函數(shù)下降方向 投影到等式約束的零空間得到可行下降方向 ，再用 2）的公式得到新內點 ? ??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 ?容易驗證 ，所以 ? ?? 0 , 0TA D X d e d??？ 任取 ，令 ， 是 的內點 1?|| ||dY e rn d???01???? ? ? ? 11? ? ? ?0 , 1TTA D X Y A D X e e Y e enn? ? ? ?? ? ? ?? ? ? ?? ? ? ?所以 是變換后問題的可行內點 ? ?? 0 , 0TA D X d e d???Y再利用 可得 n??Y又因為 ? ? ? ? ? ?? ?? ? ? ?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??? ????（近似目標有改進） ?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算法的收斂性與復雜性 定理：用 表示初始可行內點，用 表示第 次迭代 后得到的可行內點，如果取 ，則成立 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 ?????? ? ? ? ?????每步迭代計算復雜性為 ，所以 Karmarkar算法 的復雜性為 （可降至 ） ? ?3On? ?4O n L ? ? n L如何將標準線性規(guī)劃問題轉化為 Karmarkar標準型？ 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標準型 ? ?1,iix Q y i? ? ?如何獲得初始可行內點？ m in. 010TTnCXAXeXX????1111m i n . 010 , 0TnnnTnnnC X M xAX Ae xe X xXx???????????（ 充分大） M其中 表示 個 1組成的向量 nne容易驗證， 是右邊問題的可行解 111 nen ??如何滿足最優(yōu)目標值等于零的要求？ 用 表示 Karmarkar標準型最優(yōu)目標值（未知），選一 *z0? Tz C X?第 次迭代開始時 ，得 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? ?? ? ? ?? ? ? ?個 作為其估計值，將目標函數(shù)變?yōu)? 此時減小 ，然后從 繼續(xù)迭代 ?z1?kX ??TC X z?如何滿足最優(yōu)目標值等于零的要求？（繼續(xù)） 另一方面，如果某次迭代后目標函數(shù)下降不夠預期值， 例如，不滿足 0e x p 5TkTCX kC X n????????說明 ，此時可提高 值 *?zz? ?z此外，還有利用對偶變量的信息解決該問題的方法 課后作業(yè) 1）證明 Karmarkar算法中的 ? ?11rnn??2）用 Karmarkar算法求解下述問題，進行兩步 迭代，列出所有中間結果 1231 2 3m in 1. 010 , 1 , 2 , 3ixxxx x xxi????? ? ???