線性互補問題的滿Newton步不可行內(nèi)點算法及其拓展.pdf

1、線性互補問題是與數(shù)學(xué)規(guī)劃密切相關(guān)的一類數(shù)學(xué)問題,在經(jīng)濟分析和平衡問題中都有廣泛的應(yīng)用.原始-對偶內(nèi)點算法是求解線性優(yōu)化問題的一類有效算法,長期以來一直受到廣泛的關(guān)注并取得了很大的進展.內(nèi)點算法不僅在理論上具有多項式收斂性,而且在實際計算中也是很有效的.隨著內(nèi)點算法適用范圍的不斷擴大,內(nèi)點算法也用來求解線性互補問題,并且取得了豐碩的成果.不可行內(nèi)點算法起始于分量都是正的一個任意點,隨著最優(yōu)性的達到可行性也隨之達到.現(xiàn)在許多著名的軟件包都是

2、使用不可行內(nèi)點算法.
　　本文主要針對單調(diào)線性互補問題和非單調(diào)線性互補問題提出了新的不可行內(nèi)點算法.這類算法最初是由 Roos對求解線性優(yōu)化問題提出來的.算法采用滿 Newton步長,每步迭代由一個可行步和若干個中心步組成.通過設(shè)計一些新的分析工具,證明了算法具有多項式迭代復(fù)雜性.
　　全文共分為四章,其具體內(nèi)容安排如下:
　　第一章介紹互補問題和內(nèi)點算法的研究概況及一些基本知識.
　　第二章是將 Roos等人最

3、近對線性優(yōu)化問題提出的滿 Newton步不可行內(nèi)點算法推廣到了單調(diào)線性互補問題,并證明了算法多項式復(fù)雜性與現(xiàn)有的不可行內(nèi)點算法的復(fù)雜性結(jié)果保持一致.
　　第三章討論了非單調(diào)線性互補問題,主要由兩部分構(gòu)成:首先,對非單調(diào)線性互補問題提出了新的原始-對偶可行內(nèi)點算法.由于算法僅用滿 Newton步,從而不需要線性搜索.其次,在前面算法的基礎(chǔ)上,將 Roos提出的滿 Newton步不可行內(nèi)點算法進一步推廣到了非單調(diào)線性互補問題.在算法的