張從軍,李 賽,呂麗霞,王月虎

(1.南京財經(jīng)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院,江蘇南京 210023)

(2.南京財經(jīng)大學(xué)管理科學(xué)與工程學(xué)院,江蘇南京 210023)

1 引言

本文研究一類特殊的變分不等式問題:尋找一點u?∈?,使得

其中u=(x,y)T,F(u)=(f(x),g(y))T,?={(x,y)|x∈X,y∈Y,Ax+By≥b}.將此類問題記作SMV I(?,F),這里X ?Rn和Y ?Rm為非空閉凸集,A∈Rl×n,B ∈Rl×m是矩陣,b∈Rl是向量,f:X→Rn,g:Y→Rm為單調(diào)映射,并且以上各量均已給定.因為映射f只取決于變量x,映射g只取決于變量y,所以被稱為是可分離帶線性約束的變分不等式問題.這類問題被廣泛應(yīng)用于研究網(wǎng)絡(luò)分析、交通運輸、圖論等領(lǐng)域.目前對于問題SMV I(?,F)的研究,首先要在線性約束條件Ax+By=b中引入拉格朗日乘子λ∈Rl,進(jìn)而得到原SMV I(?,F)的等價形式如下:求w?∈Z,滿足(w?w?)TQ(w?)≥ 0,w∈Z,其中w=(x,y,λ)T,Q(w)= ?f(x)?ATλ,g(y)?BTλ,Ax+By ?b￠T,Z=X × Y × Rl. 接著再對該等價形式進(jìn)行求解.

交替方向法(ADM)是用來求解原問題SMV I(?,F)最經(jīng)典的算法.一直以來,如何快速求解兩個子變分不等式問題成了考查ADM有效性的關(guān)鍵,為此很多學(xué)者作了大量工作,對ADM 進(jìn)行了相應(yīng)的改進(jìn)[1?5].雖然提出的各種改進(jìn)策略在一定程度上有效提高了ADM的計算速度,但需要注意的是,此類改進(jìn)的方法并沒有完全避免求解子變分不等式問題.因為從計算角度上看,在大部分情況下,直接求解變分不等式并不是件容易的事情.為了能更好的提出新混合算法,接下來我們介紹對數(shù)二次臨近點法.對數(shù)二次臨近點算法(LQP)[6?11]主要用于求解如下這樣一類變分不等式問題,即找一點u?∈?,滿足(u?u?)TF(u?)≥ 0,?u ∈ ?,其中這里矩陣A∈Rm×n,向量b∈Rm,Y為Rm中的閉凸子集,f:Rn→Rn是連續(xù)單調(diào)映射.LQP在每次迭代時只需解決這樣一個非線性方程組

一般而言,求解一個非線性方程組比一個變分不等式組更容易操作.盡管此方法是對子問題進(jìn)行非精確求解,但是相對于精確求解子問題,非精確求解更可行、快速.因為從數(shù)值計算角度分析,精確求解一個子問題往往不太容易實現(xiàn).考慮到這個方法求解較容易的特點,LQP方法值得關(guān)注和借鑒.基于上面的考慮,本文提出了一種新的混合算法.此算法在預(yù)測步只需求解一系列相關(guān)聯(lián)的非線性方程組,而不是去處理一系列的子變分不等式問題.同時這樣做還可以在可行集中產(chǎn)生一個內(nèi)點序列,在一定程度上提高了算法的有效性和可行性:在修正步中,修正值是由當(dāng)前預(yù)測點和一個投影算子構(gòu)成的凸組合得到的.這樣保證了如果前一個迭代點是內(nèi)點,那么這樣一個凸組合得到的下一個迭代點也將會是內(nèi)點.另一方面需要注意的是,當(dāng)可行集為簡單集時,投影算子更容易執(zhí)行.

本文結(jié)構(gòu)如下:第2節(jié)主要概述了本文所需要的預(yù)備知識,參見文獻(xiàn)[12–15];第3節(jié)在映射單調(diào)和原變分不等式解集非空的條件下提出一種新的混合算法,并給出算法的一些性質(zhì),相關(guān)證明技巧參見文獻(xiàn)[16–21];第4節(jié)和第5節(jié)分析了新算法的收縮性及全局收斂性,參見文獻(xiàn)[22–26];第6節(jié)利用數(shù)值算例驗證了算法的有效性.

2 預(yù)備知識

令P?(·)為Rn到?上的投影映射,即P?(x)=argmin{ky?xk|y∈?}.投影映射有如下重要性質(zhì).

引理1[6]若??Rn為一非空閉凸子集,P?(·)為Rn到?上的投影映射,對于任意的x,y∈Rn,任意z∈?,有

定義1集合??Rn,設(shè)f是?→Rn的映射,如果f滿足(x?y)T(f(x)?f(y))≥0,?x,y∈?,則稱f在?上是單調(diào)的.若不等號嚴(yán)格成立,則稱f在?上是嚴(yán)格單調(diào)的.

3 算法的設(shè)計和性質(zhì)

以下給出新的LQP-ADM[11?24]混合算法用于求解可分離帶線性約束的變分不等式問題的步驟,然后給出此算法的一些性質(zhì).算法的步驟如下.

步0 令 ε>0,μ1,μ2∈(0,1),t∈(0,1),k=0,w0=(x0,y0,λ0)∈X ×Y ×Rl,H 為一給定的l×l階對稱正定矩陣,X ?Rn和Y?Rm為非空閉凸集,A∈Rl×n,B∈Rl×m是矩陣,b∈Rl是向量,f:X→Rn,g:Y→Rn為單調(diào)映射.

下面的符號類似.

步1.3

步3計算步長

觀察新算法的預(yù)測步可知,此算法的主要任務(wù)是解下面兩個非線性方程的近似解:帶入點 ?xk,yk,λk￠求解 x,

帶入點 ?xk+1,yk,λk￠求解 y,

比較(3.5),(3.6)兩式的共同點就相當(dāng)于求解如下方程的近似解

其中 uk=(m1,m2,···,mn),u=(w1,w2,···,wn),

引理2[6]如果q(u)為Rn上的單調(diào)映射,則對于給定的uk∈,方程(3.7)存在唯一的u∈.

因為(x),g(y)分別是關(guān)于x和y的單調(diào)映射,所以由此性質(zhì)可知非線性方程(3.5)和(3.6)都有唯一的解.

則對任意v≥0,有下面不等式成立:

其中

證 令v=(vx,vy,vλ),則(3.8)式證明包括下面三個不等式的證明:

不失一般性,可以將不等式(3.10)中的x,xk,qx,vx簡化為實數(shù).因為x>0,xk>0,vx>0,故有.結(jié)合方程組(3.8)有

則(3.10)式得證.同理可證得(3.11)式也是成立的.下面來證明(3.12)式,由方程組(3.8)可得則(3.12)式得證.綜上所述,要證的不等式成立.證畢.

下面給出一個引理來解釋算法中的停機(jī)準(zhǔn)則.

同理可得

4 算法的收縮性

本節(jié)準(zhǔn)備給出任取w?=(x?,y?,λ?)∈W?,由上面的LQP-ADM 混合算法得到的序列滿足

我們先來探討提出的LQP-ADM混合算法的預(yù)測步.

證 因為 w?=(x?,y?,λ?)是 SMV I(?,F)的解,所以

以及Ax?+By?=b在上面的兩個不等式中,分別令,則

另一方面,因為(3.5)式及下面的恒等變形

所以根據(jù)引理3可得

將(4.2)式與(4.4)式相加

又因為f(x)是單調(diào)映射,則

即

同樣由(3.2)式及引理3可得

將(4.3)與(4.6)式相加有

又因為g是關(guān)于y單調(diào)的,則

則

將(4.5)與(4.7)式相加有

得證.

于是如果考慮(4.8)式,則可得到如下引理.

證 將(4.8)式代入引理5中有

即

證畢.

由上面的引理可得到關(guān)于LQP-ADM混合算法預(yù)測步的定理如下.

其中

證 由引理6可知

同時有

將(4.9)式與此恒等式相加可得

于是

得證.

將定理1的結(jié)論作簡單變形可得到以下推論.

證 由定理1可得

于是

得證.

基于以上對混合算法中預(yù)測步的討論,結(jié)合算法的修正步可得到算法的收縮性定理如下.

證 由式(3.4)得到

利用柯西-施瓦茨不等式和投影的非擴(kuò)張性,可推出

再結(jié)合推論1可得

得證.

5 算法的收斂性

在證明算法的全局收斂性之前,先給出一個重要的引理.

其中

將此不等式右端變形為

基于對LQP-ADM混合算法收縮性的討論,接下來給出此算法的全局收斂性分析.

證 此定理可以分兩步來證:首先利用已經(jīng)得到的結(jié)論證明w∞是SMV I(?,F)的解,然后再證明序列'“收斂于w∞.

步1由定理2可得

因為 μ1,μ2,t∈ (0,1),所以

由(5.5)式可知必定存在常數(shù)c>0,使得

進(jìn)而有

故

于是

結(jié)合(5.3)式和(5.4)式可得

則

進(jìn)而由(5.1),(5.2)及(5.7)式可得

令w∞為的一個聚點且其中一個子列'“收斂于w∞.則由(5.7)及(5.8)式可得

因此

即(w?w∞)TQ(w∞)≥0,?w∈Z,這說明w∞是SMV I(?,F)的解.

步2對于SMV I(?,F)的所有解都滿足不等式(5.6),所以可推出

所以?k≥l,由(5.11)式可得

6 數(shù)值實驗

為了考察LQP-ADM混合算法的數(shù)值表現(xiàn),用Matlab軟件編程來進(jìn)行數(shù)值實驗,所有程序在Windows 2007系統(tǒng)下進(jìn)行.考慮這樣一個優(yōu)化問題,其中

為了保證問題的可行性,kbk≤r1+r2必須滿足.比如選取r1=0.5kbk,r2=0.6kbk.

引入輔助變量y,則上述問題轉(zhuǎn)化后的形式如下:

其中Br表示圓心為原點、半徑為r的圓.

接著將上述凸規(guī)劃問題轉(zhuǎn)化為可分離帶線性約束的變分不等式問題,即找一點u?∈?,滿足,其中

由于向量c與向量b的元素均是隨機(jī)產(chǎn)生的,所以每次運行LQP-ADM混合算法求得變分不等式的解都不相同,但是解均是收斂的并且收斂性態(tài)是一致的.為了說明情況,從多次運行結(jié)果中選取下面三組圖――圖1、圖2與圖3來分析.從這三組圖可知,x與λ的收斂趨勢是一樣的,都是隨著迭代次數(shù)的增加其中一個分量增大另一分量減小,但是y的收斂趨勢卻不同,圖1中y的兩個分量隨著不斷迭代都是增大的,圖2中都是減小的,而圖3中卻是一個增大另一個減小,同時容易看出新算法的收斂速度很快,所以LQP-ADM混合算法求解問題SMV I(?,F)的解是收斂的,也是有效的.

圖1:所求點的收斂曲線1

圖2:所求點的收斂曲線2

圖3:所求點的收斂曲線3