一種改進的求解單調(diào)變分不等式的平行分裂算法

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

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

1 引言

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

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

(1)

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

(2)

其中X?Rn1,Y?Rn2,A∈Rm×n1,B∈Rm×n2是給定的矩陣，b∈Rm是給定的向量，f:Rn1→Rn1,g:Rn2→Rn2是單調(diào)算子，對線性約束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是一個給定的對稱正定矩陣,可看做是對約束條件的罰參數(shù),因此(1)-(2)的解是由求解一系列的(5)-(6)這樣的低錐子單調(diào)問題得到的,而在許多實際問題中,它的求解釋相當困難的.經(jīng)典的交替方向法在文獻中都已經(jīng)有深入的研究,可看參考文獻[1,2,5,6].

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

(8)

(9)

(10)

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

(11)

(12)

(13)

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

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

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

(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的單調(diào)性得

(30)

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

(31)

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

(32)

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

(33)

(34)

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

證明: 由(34)知道

4 數(shù)值試驗

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

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

則它可以轉(zhuǎn)化為如下的形式

s.tX-Y=0,

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

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 結(jié)論

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