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

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

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

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

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

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