一種改進的求解單調變分不等式的平行分裂算法

陳小彪,張玫玉,高玉潔,寇 靜

(太原工業學院 理學系, 山西 太原 030008)

1 引言

自從二十世紀六十年代以來,有限維變分不等式的理論和算法得到了迅速的發展,并且廣泛地應用到經濟平衡理論,交通運輸,社會經濟模型,凸優化等方面.因此,變分不等式問題的研究和應用已經成為了數學中的一個熱點問題. 一個變分不等式問題就是找到一個向量u*∈Ω使得

(u-u*)TF(u*)≥0,?u∈Ω

(1)

其中Ω是Rn中的一個非空閉凸集，F是從Rn到它自身的一個映射，在本文中我們考慮如下結構的變分不等式問題：

(2)

其中X?Rn1,Y?Rn2,A∈Rm×n1,B∈Rm×n2是給定的矩陣，b∈Rm是給定的向量，f:Rn1→Rn1,g:Rn2→Rn2是單調算子，對線性約束Ax+Bx=b引入拉格朗日乘子λ∈Rm,則(1)-(2)可表示為如下的緊湊形式(參考文獻[1,2]):

找到一個向量w*=(x*,y*,λ)∈W使得

(w-w*)TF(W*)≥0,?w∈W

(3)

(4)

我們用W*表示(3)-(4)的解.

(5)

(6)

(7)

其中H∈Rm×m是一個給定的對稱正定矩陣,可看做是對約束條件的罰參數,因此(1)-(2)的解是由求解一系列的(5)-(6)這樣的低錐子單調問題得到的,而在許多實際問題中,它的求解釋相當困難的.經典的交替方向法在文獻中都已經有深入的研究,可看參考文獻[1,2,5,6].

近來，一些漸進交替方向法PADM也得到了廣泛的研究[7,8,9],特別的,在文獻[7]中的PADM通過如下方法得到新的迭代點：

(8)

(9)

(10)

其中r,s大于0,可看做是漸進參數,則(8)-(9)是強單調變分不等式.文獻[8]對這種漸進交替方向法做了改進,找到了一個下降方向和相應的最優步長.

(11)

(12)

(13)

在每一次的迭代中(11)和(12)可以同時進行,這也是稱它為平行分裂算法的原因.而(11)和(12)也只是單調的變分不等式,在實際情況中求解釋相當困難的,受到文獻[7]的啟發,我們在子問題(11)和(12)中加入漸近項,則它們變為強單調的變分不等式,使得求解相對容易,并找到一個下降方向和沿著這個下降方向的最優步長,通過修正步來得到新的迭代點.

在整篇文章中,我們做出如下的假設:

(1)f(x)和g(y)是單調的,即

(x-x′)T(f(x)-f(x′))≥0,?x,x′∈K

(y-y′)T(f(y)-f(y′))≥0,?y,y′∈Y

(2)文中提到的變分不等式都是可解的,且解集非空.

2 改進的平行分裂算法

為了后面證明的方便,我們記

(14)

對給定的點wk=(xk,yk,λk)∈W,本文通過如下方法得到新的迭代點：

(15)

(16)

(17)

新算法

Step 0 ?ε>0, 初始點w0=(x0,y0,λ0)∈Rn1×Rn2×Rm,G是(14)中所定義的矩陣，k=0

(18)

(19)

(20)

3 收斂性證明

(21)

證明:利用柯西施瓦茲不等式得

(22)

(23)

(24)

則由(22),(23),(24)得

(25)

(26)

(27)

由(15),(16),(17)可得

(28)

(29)

(26)和(28)相加并利用f的單調性得

(30)

(27)和(29)相加并利用g的單調性得

(31)

(30)和(31)相加并利用Ax*+By*=b易得(25).證畢.

(32)

把(25)和(32)相加可得

(33)

(34)

定理3.1w*=(x*,y*,λ*)∈W*,wk=(xk,yk,λk)是由新算法產生的序列點,則它滿足

證明: 由(34)知道

4 數值試驗

我們考慮矩陣的逼近問題,其數學模型如下

C，HL和HU是給定的n×n對稱矩陣.

則它可以轉化為如下的形式

s.tX-Y=0,

根據最優性條件,它可以寫成變分不等式的形式來求解.在實驗中，我們取H=5I,γ=1.5,R=S=5,初始條件X=Y=λ=0,ε=10-5,文獻[8][10]中的算法我們分別稱為IPADM和PSM 計算結果如下

IPADM在[8]PSM在[10]新算法nNo.CPUNo.CPUNo.CPU50940.1791100.197920.175100851.0511151.170850.9823008310.75113617.793809.9005008636.70417581.2208132.98480085156.081204480.65883147.240100092364.750215739.36187328.008

5 結論

本文所證明的算法和文獻[8]的區別在于子問題(15)-(17)的求解可以同時進行，而和文獻[10]的區別在于它在求解子問題(15)-(17)時加入了漸近項,結合了交替方向法和鄰近點分解算法的優點,且新算法同樣適合并行計算,并得到了新算法的下降方向和最優步長.如何利用這種新的分解算法的優點來設計混合算法是需要進一步研究的問題.