一種混合算法求解可分離帶線性約束的變分不等式問題

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

(1.南京財經大學應用數學學院,江蘇南京 210023)

(2.南京財經大學管理科學與工程學院,江蘇南京 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為單調映射,并且以上各量均已給定.因為映射f只取決于變量x,映射g只取決于變量y,所以被稱為是可分離帶線性約束的變分不等式問題.這類問題被廣泛應用于研究網絡分析、交通運輸、圖論等領域.目前對于問題SMV I(?,F)的研究,首先要在線性約束條件Ax+By=b中引入拉格朗日乘子λ∈Rl,進而得到原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. 接著再對該等價形式進行求解.

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

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

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

2 預備知識

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

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

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

3 算法的設計和性質

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

步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為單調映射.

下面的符號類似.

步1.3

步3計算步長

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

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

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

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

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

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

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

其中

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

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

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

下面給出一個引理來解釋算法中的停機準則.

同理可得

4 算法的收縮性

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

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

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

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

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

所以根據引理3可得

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

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

即

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

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

又因為g是關于y單調的,則

則

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

得證.

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

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

即

證畢.

由上面的引理可得到關于LQP-ADM混合算法預測步的定理如下.

其中

證 由引理6可知

同時有

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

于是

得證.

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

證 由定理1可得

于是

得證.

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

證 由式(3.4)得到

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

再結合推論1可得

得證.

5 算法的收斂性

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

其中

將此不等式右端變形為

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

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

步1由定理2可得

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

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

進而有

故

于是

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

則

進而由(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 數值實驗

為了考察LQP-ADM混合算法的數值表現,用Matlab軟件編程來進行數值實驗,所有程序在Windows 2007系統下進行.考慮這樣一個優化問題,其中

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

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

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

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

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

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

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

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