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

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

1 引言

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

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

(1)

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

(2)

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

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

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

(3)

(4)

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

(5)

(6)

(7)

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

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

(8)

(9)

(10)

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

(11)

(12)

(13)

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

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

(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 改進(jìn)的平行分裂算法

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

(14)

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

(15)

(16)

(17)

新算法

Step 0 ?ε>0, 初始點(diǎn)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)生的序列點(diǎn),則它滿足

證明: 由(34)知道

4 數(shù)值試驗(yàn)

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

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

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

s.tX-Y=0,

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

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