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

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

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

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