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

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

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

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