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

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

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

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