對(duì)稱錐互補(bǔ)問題若干內(nèi)點(diǎn)算法的復(fù)雜性研究.pdf

1、上世紀(jì)60年代以來大量的理論和實(shí)踐結(jié)果表明,內(nèi)點(diǎn)算法是解決優(yōu)化問題,互補(bǔ)問題最有效的方法之一.本論文旨在研究幾類對(duì)稱錐線性互補(bǔ)問題(包括非單調(diào)線性互補(bǔ)問題,半定互補(bǔ)問題和非單調(diào)對(duì)稱錐線性互補(bǔ)問題）中的有效內(nèi)點(diǎn)算法,討論它們的算法復(fù)雜性和實(shí)際計(jì)算效果.
　　本文首先給出基于寬鄰域的三個(gè)非單調(diào)線性互補(bǔ)問題的預(yù)估-矯正內(nèi)點(diǎn)算法,其中前兩個(gè)是Mehrotra型算法,“保障”策略的實(shí)施使得算法具有多項(xiàng)式收斂性.相對(duì)第一個(gè)算法,第二個(gè)算法中通

2、過設(shè)計(jì)新的中心參數(shù)更新方案不僅簡(jiǎn)化了復(fù)雜性分析,保證了Mehrotra型算法的多項(xiàng)式收斂性,而且也具有更好的實(shí)際計(jì)算效果.通過證明一些重要的引理,前兩種算法對(duì)于可行的初始點(diǎn),都具有O((1+κ)nL)算法復(fù)雜性.接著,通過線性互補(bǔ)問題以及一個(gè)不可行的初始點(diǎn),構(gòu)造出線性互補(bǔ)問題的擾動(dòng)問題,提出了線性互補(bǔ)問題的二階不可行預(yù)估-矯正內(nèi)點(diǎn)算法.在求解該擾動(dòng)問題的過程中,算法產(chǎn)生的迭代點(diǎn)對(duì)于擾動(dòng)問題始終是嚴(yán)格可行的,對(duì)于原問題卻始終不可行.該算法

3、采用1-范數(shù)寬鄰域,并對(duì)矯正步搜索方向進(jìn)行修正.最終證明該算法具有O((1+κ)nL)的算法復(fù)雜性,這和目前為止最好的不可行內(nèi)點(diǎn)算法復(fù)雜性一致,數(shù)值結(jié)果驗(yàn)證了算法具有很好的實(shí)際計(jì)算效果.進(jìn)一步,把該算法推廣到半定線性互補(bǔ)問題,得到了與線性互補(bǔ)問題一致的算法復(fù)雜性結(jié)果.
　　接著深入研究了兩個(gè)不可行的對(duì)稱錐線性互補(bǔ)問題預(yù)估-矯正內(nèi)點(diǎn)算法. Mehrotra型內(nèi)點(diǎn)算法的特點(diǎn)是在計(jì)算矯正方向時(shí)用到預(yù)估方向的乘積.在嚴(yán)格可行解存在的假設(shè)下

4、,通過對(duì)預(yù)估方向乘積賦予不同的權(quán)重修正矯正方向,提出Cartesian-P*(κ)對(duì)稱錐線性互補(bǔ)問題的Mehrotra型內(nèi)點(diǎn)算法,此算法始于不可行的初始點(diǎn).為了在每一步迭代中可行性殘量與互補(bǔ)間隙有相同的減小率,該算法采用不同于傳統(tǒng)矯正步的計(jì)算方法.基于NT尺度,該算法具有算法復(fù)雜性O(shè)((1+κ)r2 logε-1.數(shù)值試驗(yàn)也驗(yàn)證了算法是有效的.接著,在解集非空有界的條件下,給出第二個(gè)預(yù)估-矯正不可行內(nèi)點(diǎn)算法.該算法通過一正定的不可行點(diǎn),

5、構(gòu)造Cartesian-P*(κ)對(duì)稱錐線性互補(bǔ)問題的擾動(dòng)問題,通過求解擾動(dòng)問題,最終得到原問題的解.基于NT尺度該算法具有O((1+κ)r2 logε-1的算法復(fù)雜性.
　　最后研究了Cartesian-P*(κ)對(duì)稱錐水平線性互補(bǔ)問題的中心路徑理論.雖然具有不同形式的標(biāo)準(zhǔn)線性互補(bǔ)問題和水平線性互補(bǔ)問題是等價(jià)的,但對(duì)于對(duì)稱錐線性互補(bǔ)問題而言卻是未決問題.在中心路徑理論的基礎(chǔ)上設(shè)計(jì)了一種不可行內(nèi)點(diǎn)算法,該算法采用中心路徑附近的點(diǎn)作