凸規(guī)劃的廣義中心路徑跟蹤算法及其拓展.pdf

1、內(nèi)點算法是求解線性規(guī)劃的有效算法之一,它具有多項式復雜性,實際計算性能也可以與單純型法媲美,尤其對大規(guī)模問題更顯高效.第一個具有實用性的多項式復雜性內(nèi)點算法是由 Karmarkar于1984年提出的.此后20多年,經(jīng)過眾多優(yōu)化專家的共同努力,對內(nèi)點算法的研究取得了豐碩成果:不僅建立了完善的理論體系,而且開發(fā)出了高效的數(shù)值軟件.如今,內(nèi)點算法被成功推廣到求解凸規(guī)劃、互補問題、半定規(guī)劃、二階錐優(yōu)化等領域.
　　本文的研究成果有以下兩個

2、方面:其一,基于Gonzaga,艾文寶等人的思想,對水平線性互補問題提出了一種新的廣義中心路徑跟蹤算法.算法從任意原始-對偶可行內(nèi)點出發(fā),在每步迭代中取“仿射步”與“中心步”的凸組合為新的迭代方向,圍繞一條廣義中心路徑趨于問題的最優(yōu)解.通過對仿射步、中心步迭代方向及其交叉項上界的估計,證明了算法的多項式迭代復雜性.其二,基于J.Peng, T.Terlaky, Y.Q.Bai等學者近期的工作,構(gòu)造了一個新的核函數(shù),設計了一類求解P線性互

3、補問題的內(nèi)點算法.該算法用核函數(shù)的障礙函數(shù)替代以往原始-對偶算法所依賴的經(jīng)典對數(shù)障礙函數(shù),得到了新算法下大步校正方法和小步校正方法的多項式迭代復雜性界.* k)(
　　本文共分四章,第一章介紹了相關(guān)基本知識及研究背景;第二章提出了水平線性互補問題的廣義中心路徑跟蹤算法,并證明了算法的多項式收斂性;第三章為P線性互補問題設計了一個基于新核函數(shù)的內(nèi)點算法,分別給出了大步校正和小步校正下的多項式迭代復雜性界;第四章是對全文的總結(jié)和展望.