線性矩陣互補(bǔ)問題的內(nèi)點(diǎn)算法.pdf

1、互補(bǔ)問題的理論和算法在經(jīng)濟(jì)學(xué)，對(duì)策論和數(shù)學(xué)規(guī)劃領(lǐng)域有著廣泛的應(yīng)用，關(guān)于互補(bǔ)問題的研究一直是非線性科學(xué)和計(jì)算科學(xué)的熱點(diǎn)問題，求解互補(bǔ)問題的算法的研究也取得了很多成果.在這些算法之中，內(nèi)點(diǎn)算法一直是個(gè)非?；钴S的研究方向.因?yàn)閮?nèi)點(diǎn)算法具有更優(yōu)越的計(jì)算復(fù)雜度，而且在實(shí)際計(jì)算中，尤其對(duì)大規(guī)模問題更顯其高效性.正是由于內(nèi)點(diǎn)算法的這種優(yōu)點(diǎn)，人們希望內(nèi)點(diǎn)算法不只是解決維向量的互補(bǔ)問題，還可以解決大規(guī)模矩陣的問題.在進(jìn)行了大量研究后， Kojima M等

2、人提出關(guān)于對(duì)稱矩陣的半定線性互補(bǔ)問題（SDLCP），并且在單調(diào)仿射子空間的假設(shè)下，構(gòu)造了以沿著中心路徑的牛頓方向?yàn)樗阉鞣较虻膬?nèi)點(diǎn)算法的理論框架. 本文主要是在Kojima M所提出的關(guān)于對(duì)稱矩陣的單調(diào)半定線性互補(bǔ)問題的理論基礎(chǔ)上，用另外一種搜索方向（NT方程組）構(gòu)造內(nèi)點(diǎn)算法來求解這個(gè)問題.Kojima M的關(guān)于對(duì)稱矩陣的SDLCP研究中，采用的中心路徑上的牛頓方向產(chǎn)生的矩陣不能保證對(duì)稱性，而Nesterov－Todd改進(jìn)后得出

3、的NT方程組是可以保持對(duì)稱性的.文中以NT方程組的解為搜索方向，分別構(gòu)造了單調(diào)線性算子條件下的路徑跟蹤法和勢(shì)函數(shù)約減法.其中路徑跟蹤法要求初始點(diǎn)在中心路徑鄰域內(nèi)，并且選取步長(zhǎng)為1的窄鄰域中心路徑.并且分析了這種窄鄰域路徑跟蹤算法的可行性及收斂性.而文中的勢(shì)函數(shù)約減法不同于先前的路徑跟蹤法，它的初始點(diǎn)只要求在嚴(yán)格可行域，使用一維搜索確定步長(zhǎng)，使得勢(shì)函數(shù)在每步迭代時(shí)都達(dá)到最優(yōu).并且討論了這種算法的可行性，確定了最小下降量，進(jìn)一步分析了計(jì)算復(fù)