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

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

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

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