錐規(guī)劃中若干內(nèi)點算法的復(fù)雜性研究.pdf

1、在內(nèi)點法中，理論和實踐之間存在著一個矛盾：實際計算效果好的算法在理論上卻具有較差的迭代復(fù)雜性。本論文旨在研究幾類錐規(guī)劃問題（包括線性規(guī)劃、半定規(guī)劃和對稱錐規(guī)劃）中有效的內(nèi)點算法，討論它們的迭代復(fù)雜性和數(shù)值效果。
　　首先給出了線性規(guī)劃的兩個Mehrotra型預(yù)估．矯正算法。它們都是基于寬鄰域的原．對偶內(nèi)點算法，并且寬鄰域的定義和常用的一∞鄰域有著密切關(guān)系。在每次迭代中，該算法比傳統(tǒng)的迭代方向增加一個矯正方向。通過證明一些重要引理，

2、給出了算法的O（√nL）迭代復(fù)雜性，其中n是問題維數(shù)，/是輸入數(shù)據(jù)的長度。這是第一次得到具有O（√nL）復(fù)雜性的Mehrotra型預(yù)估-矯正算法，這也是目前內(nèi)點法中最好的復(fù)雜性結(jié)果?；诰€性規(guī)劃問題的標(biāo)準(zhǔn)測試問題集NETLIB的數(shù)值結(jié)果顯示了該算法具有很好的實際計算效果。隨后，把第一個算法推廣到了半定規(guī)劃問題?；贜T方向，證明了算法的復(fù)雜性與線性規(guī)劃的情況是相同的。并且，基于實際問題的數(shù)值結(jié)果驗證了算法的實際有效性．
　　接著深

3、入研究了線性規(guī)劃問題的帶保障的Mehrotra型預(yù)估．矯正算法。該算法把Mehrotra算法和一個保障策略結(jié)合起來，以保證迭代既不超出給定的鄰域又能獲得較大的迭代步長。指出了Koulaei和Te rlaky在推廣帶保障的Mehrotra型預(yù)估．矯正算法到半定規(guī)劃時存在的一個嚴(yán)重證明錯誤。通過修改預(yù)估步中的最大步長的計算方法，給出了半定規(guī)劃的一個新的Mehrotra型預(yù)估．矯正算法。但對于線性規(guī)劃的情況，由新方法計算的預(yù)估步長與Koula

4、ei和Terlaky的方法是完全相同的?；贜T方向，證明該算法的復(fù)雜性為O(nL)。然后，利用歐氏Jordan代數(shù)作為工具，把該算法進一步推廣到對稱錐（包含了非負(fù)卦限，半正定矩陣錐和二階錐），并證明了算法的O(rlogε-1)迭代復(fù)雜性，其中r是Jordan代數(shù)的秩，ε是精度參數(shù)。同時提出了一個新的自適應(yīng)更新中心策略，基于該策略的Mehrotra型預(yù)估．矯正算法和帶保障的Mehrotra算法具有相同的復(fù)雜性。數(shù)值結(jié)果證實了新算法的有效

5、性。利用類似的技巧，把Salahi和Mahdavi-Amiri提出的二階Mehrotra型預(yù)估．矯正算法由線性規(guī)劃推廣到了對稱錐規(guī)劃。但是，推廣的算法在迭代步長的選取方式和保障的使用范圍都不同于Salahi和Mahdavi-Amiri的算法?；贜T方向，證明了算法的復(fù)雜性與線性規(guī)劃的情況是相同的。然后，又給出了該算法的一個不可行算法，基于NT方向，不可行算法具有O(r2logε-1)迭代復(fù)雜性；若初始點是可行點，則算法的復(fù)雜性降低到O

6、(rlogε-1)。
　　最后，基于艾文寶和張樹中的原．對偶路徑跟蹤算法，提出了對稱錐規(guī)劃的一個新的原．對偶不可行內(nèi)點算法?；凇翱山粨Q類”方向，證明了該算法的多項式收斂性。特別的，對于NT方向，復(fù)雜性為O(r1.5logε-1)；對于xs和sx方向，復(fù)雜性為O(r2logε-1)。如果算法的初始點是可行點，則對于NT方向，復(fù)雜性為0(√rlogε-1)；對于xs和sx方向，復(fù)雜性為O(rlogε-1)。當(dāng)取NT方向時，我們首次得