對稱錐互補問題若干內點算法的復雜性研究.pdf

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

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

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

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

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