一類新的半正定規(guī)劃和二次錐規(guī)劃的原始-對偶內(nèi)點算法.pdf

1、自從Karmarkar在1984年提出了求解線性規(guī)劃問題的多項式時間內(nèi)點算法：一個里程碑性的工作，由于對大規(guī)模優(yōu)化問題求解的有效性及在多領(lǐng)域的應(yīng)用使得內(nèi)點算法成為數(shù)學(xué)規(guī)劃最活躍的研究領(lǐng)域之一.大步校正方法和小步校正方法是兩類重要的多項式時間內(nèi)點算法.在理論上，基于經(jīng)典對數(shù)障礙函數(shù)小步校正方法的理論復(fù)雜性以√n優(yōu)越于大步校正方法，其中n是問題的不等式約束個數(shù).但是在實踐中，大步校正方法的實現(xiàn)遠比小步校正方法有效.這就是所謂的內(nèi)點算法的不合

2、理性(IronyofInterior-PointMethods)問題. 本文介紹一類新的基于Non-Self-Regular核函數(shù)半正定規(guī)劃問題的原始-對偶內(nèi)點算法而且減小了大步校正方法在理論與實踐之間的間隙(Gap).由Non-Self-Regular核函數(shù)構(gòu)造新障礙函數(shù)，并用新障礙函數(shù)代替經(jīng)典對數(shù)障礙函數(shù).分析顯示新障礙函數(shù)不僅可以定義搜索方向而且可以控制內(nèi)迭代的過程.和Self-Regular核函數(shù)相比，Non-Self-

3、Regular核函數(shù)缺少了強凸性.為了克服這個困難，作者根據(jù)新障礙函數(shù)的性質(zhì)，介紹了新的分析工具來分析算法的復(fù)雜性.并成功地應(yīng)用到半正定規(guī)劃的原始-對偶內(nèi)點算法的復(fù)雜性分析中，相比中基于Self-Regular核函數(shù)的分析，作者的分析方法是簡單和直觀的.最后，分別得出迄今為止關(guān)于半正定規(guī)劃問題的大步校正和小步校正原始-對偶內(nèi)點算法的最好理論迭代界為：O(√nlogn)logn/ε和O(√n)logn/ε. 完成半正定規(guī)劃問題的原

4、始-對偶內(nèi)點算法的設(shè)計和復(fù)雜性分析后，作者又轉(zhuǎn)向研究二次錐規(guī)劃問題的原始-對偶內(nèi)點算法.類似在半正定規(guī)劃中的設(shè)計和分析方法，用障礙函數(shù)代替經(jīng)典對數(shù)障礙函數(shù)并介紹新的分析工具.最后，成功地應(yīng)用到二次錐規(guī)劃的原始-對偶內(nèi)點算法的設(shè)計和復(fù)雜性分析中，得到迄今為止關(guān)于二次錐規(guī)劃問題的大步校正和小步校正原始-對偶內(nèi)點算法的最好理論迭代界為：O(√NlogN)logN/ε和O(√N)logN/ε. 綜上所述，本文分別設(shè)計和分析了關(guān)于半正定規(guī)

5、劃及二次錐規(guī)劃的原始-對偶內(nèi)點算法.新的算法不僅縮小了大步校正原始-對偶內(nèi)點算法在理論與實踐之間的間隙(Gap)，而且分別得出迄今為止關(guān)于半正定規(guī)劃及二次錐規(guī)劃的大步校正和小步校正原始-對偶內(nèi)點算法的最好理論迭代界.數(shù)值試驗結(jié)果亦表明基于Non-Self-Regular核函數(shù)的半正定規(guī)劃和二次錐規(guī)劃的原始-對偶內(nèi)點算法是非常有效的. 全文安排如下：第一章，引言；第二章，新核函數(shù)；第三章，基于新核函數(shù)的半正定規(guī)劃的原始-對偶內(nèi)點算