P-,--(κ)線性互補(bǔ)問題寬鄰域原始-對(duì)偶內(nèi)點(diǎn)算法研究.pdf

1、1984年，N．Karmarkar提出了線性規(guī)劃的一種新的多項(xiàng)式算法，該算法不僅比橢球算法具有更優(yōu)越的計(jì)算復(fù)雜性，而且在實(shí)際計(jì)算中也可以與單純形法相媲美，尤其對(duì)大規(guī)模問題更顯其高效性．與單純形算法沿著可行區(qū)域的邊界尋優(yōu)不同，Karmarkar算法是建立在單純形結(jié)構(gòu)之上的，它是從初始內(nèi)點(diǎn)出發(fā)，沿著最速下降方向，從可行區(qū)域內(nèi)部逐漸走向最優(yōu)解．因此Karmarkar算法又被稱為內(nèi)點(diǎn)算法．自從Karmarkar劃時(shí)代的論文發(fā)表以來，內(nèi)點(diǎn)算法一直

2、是數(shù)學(xué)規(guī)劃領(lǐng)域一個(gè)非?；钴S的研究方向． 互補(bǔ)問題的理論和算法在經(jīng)濟(jì)學(xué)，對(duì)策論和數(shù)學(xué)規(guī)劃領(lǐng)域有著廣泛的應(yīng)用，關(guān)于互補(bǔ)問題的研究一直是非線性科學(xué)和計(jì)算科學(xué)的熱點(diǎn)問題，求解互補(bǔ)問題的算法的研究也取得了很多成果。1991年,Kojima等人將已有的線性規(guī)劃結(jié)論都推廣到更一般的陣線性互補(bǔ)問題上，此后，線性規(guī)劃內(nèi)點(diǎn)算法能否推廣到陣線性互補(bǔ)問題上成了衡量這種算法好壞的標(biāo)準(zhǔn)之一．因此，對(duì)陣線性互補(bǔ)問題算法的研究具有重要意義． 本論文重點(diǎn)

3、研究陣線性互補(bǔ)問題和陣水平線性互補(bǔ)問題兩種重要的非單調(diào)線性互補(bǔ)問題，針對(duì)上述兩種互補(bǔ)問題，提出了幾種寬鄰域內(nèi)點(diǎn)算法，詳細(xì)分析了所給算法的迭代復(fù)雜性．全文各部分內(nèi)容安排如下： 第一章為緒論。首先給出了互補(bǔ)問題的基本理論，然后介紹了內(nèi)點(diǎn)算法的產(chǎn)生與研究現(xiàn)狀。 第二章對(duì)陣線性互補(bǔ)問題提出了一種基于寬鄰域的勢(shì)函數(shù)約減算法，在較一般的情況下證明了算法的多項(xiàng)式復(fù)雜性． 第三章給出陣線性互補(bǔ)問題的一種基于鄰近度量函數(shù)最小值的預(yù)