一個解變分不等式問題的非單調(diào)Broyden-like算法

(武夷學(xué)院數(shù)學(xué)與計算機學(xué)院，福建 武夷山 354300)

1 預(yù)備知識

考慮變分不等式問題(簡記VI(X,F))[1-5]：求向量x*∈X，使得對于任意的x∈X有：

(x-x*)TF(x*)≥0，

(1)

成立。 其中，向量函數(shù)F(x):Rn→Rn為連續(xù)可微函數(shù)。

2010年，Zhang、Liu等人提出了可行域[1]：X={x|Ax>b,x∈Rn,A∈Rm×n,b∈Rm}的VI(X,F)，記D=AT，文中的VI(X,F)皆是該類VI(X,F)，其KKT系統(tǒng)為：F(x)-Dy=0,yT(Ax-b)=0,y≥0,Ax-b≥0。記s=Ax-b，則有

F(x)-Dy=0,s=Ax-b,y≥0,s≥0,yTs=0。

(2)

采用Fischer-Burmeister(FB)函數(shù)[6-7]：

將式(2)等價轉(zhuǎn)化為方程組問題，即

(3)

其中，

(4)

顯然函數(shù)φFB(a,b)=0?a≥0,b≥0,ab=0，但是FB函數(shù)在點(0,0)處不可微，通過引入光滑參數(shù)μ>0，得到一個光滑F(xiàn)B函數(shù)：

(5)

那么，φ(0,a,b)=φFB(a,b)。

令z=(μ,x,y,s)∈R++×Rn×Rm×Rm，

(6)

(7)

那么式(2)等價于以下方程組問題：

H(z)=0。

(8)

通過計算，得

(9)

其中，

μΘ(μ,y,s)=vec{[φ(μ,yi,si)]′μ:i∈N}，

(10)

(11)

(12)

那么可得，對于任意的i=1,2,…,m，有

0≤[φ(μ,yi,si)]′yi≤e3μ+5μ，0≤[φ(μ,yi,si)]′si≤e3μ+5μ。

引理1設(shè)函數(shù)H(z)由式(6)定義，則下面結(jié)論成立。

1)對于任意的z∶=(μ,x,y,s)∈R++×Rn×Rm×Rm，函數(shù)H(z)是連續(xù)可微的；

下文中的矩陣A均為列滿秩矩陣。

2 非單調(diào)Broyden-like算法

本節(jié)建立了求解由式(8)定義的方程H(z)=0的非單調(diào)Broyden-like算法。 定義價值函數(shù)：

f(z)=||H(z)||。

(13)

顯然，有f(z)=0?x是VI(X,F)的解。

下面給出算法的具體步驟。

算法1(解VI(X,F)的非單調(diào)Broyden-like算法)

步驟2 若f(zk)=0，算法結(jié)束；否則，計算

βk∶=β(zk)=γmin{1,f(zk)2},

(14)

并求解下列方程組：

(15)

得向量組Δzk， 其中Bk為由式(9)定義的H(zk)的近似矩陣。

步驟3 若不等式

f(zk+Δzk)≤αf(zk)-σ||Δzk||2，

(16)

成立，令λk∶=1且轉(zhuǎn)步驟5。

步驟4mk為使得下式成立的最小非負整數(shù)m，

f(zk+δmΔzk)≤Ck-σ1‖δmΔzk‖2-σ2δmf(zk),

(17)

則令λk=δmk,其中

(18)

且ρk∈[ρmin,ρmax],轉(zhuǎn)步驟5。

步驟5 令zk+1:=zk+λkΔzk。

步驟6 更新Bk得到Bk+1

(19)

注：非單調(diào)線搜索式(17)由Gu和Mo在文獻[8]首次給出，式(18)中若ρk=0，那么非單調(diào)線搜索轉(zhuǎn)化為文獻[9]中提出的單調(diào)線搜索。

引理2算法1是適定的。即對于所有的k≥0，必存在一個非負整數(shù)mk使得非單調(diào)線搜索式(17)成立。

證明 當(dāng)λk→0+時，顯然有f(zk)≤Ck。

由C0的定義，可知當(dāng)k=0時結(jié)論成立。 假設(shè)f(zk)≤Ck，下面證明f(zk+1)≤Ck+1。 下面分兩種情況進行討論。

情況一 若式(16)成立，那么f(zk+Δzk)≤αf(zk)≤f(zk)≤Ck。

情況二 若算法1運行了式(17)，那么f(zk+1)≤Ck-σ1||λkΔzk||2-σ2f(zk)≤Ck。

那么，可得式f(zk+1)≤Ck成立，結(jié)合式(18)，可得

f(zk+1)-Ck+1=ρk+1(f(zk+1)-Ck)≤0。

(20)

綜上可得，對于任意的k≥0有f(zk)≤Ck。 證畢。

由引理2，可得：

推論1 若序列{zk}由算法1迭代生成，那么對于任意的k≥0，有

f(zk)≤Ck。

(21)

引理3設(shè)H(·)以及β(·)分別由式(6)和式(14)定義，那么

證明參見文獻[10]引理5。

3 收斂性分析

本節(jié)討論算法1的全局收斂性和局部超線性/二次收斂性。 為了分析算法1的收斂性，給出下述假設(shè)：

假設(shè)1

1)水平集Ω={z∈R++×Rn×Rm×Rm|f(z)≤f(z0)}有界；

2)矩陣H′(z)在集合Ω中是Lipschitz連續(xù)的，即存在常數(shù)l>0使得

||H′(z1)-H′(z2)||≤l||z1-z2||,?z1,z2∈Ω；

3)對于任意的z∈Ω，矩陣H′(z)為非奇異矩陣。

引理4設(shè)序列{zk}由算法1迭代生成，那么序列{Ck}是非增單調(diào)的，且{zk}?Ω。

證明參見文獻[10]引理6。

引理5若假設(shè)1成立，設(shè)序列{zk}為由算法1迭代生成的序列，那么

方便起見，定義

(22)

那么，有yk=Ak+1ιk，其中yk=H(zk+1)-H(zk)且ιk=λkΔzk。 由Bk+1的更新公式，有

(23)

更進一步，令

(24)

那么，

(25)

下面的引理來源于文獻[11]的引理2.6。

那么

(26)

特別地，序列{ζk}的一個子列趨于0。 此外，若

(27)

那么

(28)

特別地，整個序列{ζk}收斂于0。

定理1若假設(shè)1成立，序列{zk}由算法1迭代生成，那么序列{zk}的任意聚點都是方程(8)的解。

證明由假設(shè)1和引理4，可知序列{zk}有界。 不失一般性，假設(shè)序列{zk}收斂于序列{zk}的聚點z*。 那么，可以得到z*滿足等式f(z*)=0。 隨后分兩種情況進行討論：

即對于所有充分大的k∈K，存在常數(shù)m1>0，有

||Δzk||≤m1f(zk)，

(29)

成立。 不妨設(shè)序列{Δzk}k∈K收斂于Δz*=(Δμ*,Δx*,Δy*,Δs*)，由式(25)，可得||(Ak+1-Bk)Δzk||=ζk||Δzk||。 對于k∈K，令k→，可得BkΔzk→H′(z*)Δz*。 另一方面，對于k∈K，令等式(15)兩邊k→，可得

H(z*)+H′(z*)Δz*=β(z*)μ*。

(30)

(31)

引理7[10]設(shè)函數(shù)F:Rn→Rn是局部Lipschitz函數(shù)，那么

1)類似于Clarke[12]，函數(shù)F有廣義雅克比 ?F(x)。 且若函數(shù)F在點x處半光滑，則在點x沿著方向h∈Rn函數(shù)F的方向?qū)?shù)F′(x;h)存在。 另外，函數(shù)F在點x∈Rn處半光滑等價于其所有的分量函數(shù)在點x∈Rn處半光滑。

2)函數(shù)F在點x處半光滑，當(dāng)且僅當(dāng)對于所有的V∈?F(x+h),h→0，有

||Vh-F′(x:h)||=o(||h||)。

另外，||F(x+h)-F(x)-F′(x:h)||=o(||h||)。

3)函數(shù)F在點x處強半光滑等價于對于所有的V∈?F(x+h),h→0，有

||Vh-F′(x;h)||=O(||h||2)。

另外，||F(x+h)-F(x)-F′(x:h)||=O(||h||2)。

引理8[10]令函數(shù)H和函數(shù)Θ分別由式(6)和式(7)定義，那么

1)函數(shù)Θ是半光滑的。

2)函數(shù)H是局部Lipschitz和半光滑的，更進一步，若函數(shù)F′(x)Lipschitz連續(xù)，那么，函數(shù)H是強半光滑的。

f(zk+Δzk)<αf(zk)-σ||Δzk||2,

(32)

成立。

||Δzk||≤M2f(zk)。

(33)

成立。 由函數(shù)H的半光滑性，對于任意的充分逼近于z*的zk，存在正常數(shù)L1，使得

f(zk)=||H(zk)-H(z*)||≤L1||zk-z*||，

(34)

成立。 另一方面，由H′(z*)的非奇異性以及序列{zk}收斂于z*，存在常數(shù)L2>0，使得

f(zk)=||H(zk)-H(z*)||≥L2||zk-z*||，

(35)

成立。 由式(34)和式(35)，有

o(||zk-z*||)=o(||H(zk)-H(z*)||)=o(||H(zk)||)。

(36)

由式(33)和式(34)，可得

||Δzk||≤M2||H(zk)-H(z*)||≤M2L1||zk-z*||。

(37)

由式(15)，得

(Ak+1-H′(zk))(zk-z*)+(Ak+1-Bk)Δzk-[H(zk)-H(z*)-H′(zk)(zk-z*)]。

那么，得

||zk+Δzk-z*||≤M1(ζkM2f(zk)+γμ0f(zk)2+o(||zk-z*||))≤

M1(ζkM2L1||zk-z*||+o(||zk-z*||))。

(38)

那么，當(dāng)zk充分逼近于z*時，得

f(zk+Δzk)≤||H(zk+Δzk)-H(z*)||≤L1||zk+Δzk-z*||≤

M3ζk||zk-z*||+o(||zk-z*||)。

(39)

f(zk+Δzk)-αf(zk)+σ||Δzk||2≤M3ζk||zk-z*||+o(||zk-z*||)-αL2||zk-z*||+

(40)

由此可得，當(dāng)zk充分逼近于z*時，有λk=1滿足式(31)。

下面分析算法1的局部超線性收斂性。

定理2若假設(shè)1成立，序列{zk}由算法1迭代生成，且z*為{zk}的聚點，那么，序列{zk}超線性收斂于z*，即||zk+1-z*||=o(||zk-z*||)。

(41)

由式(35)，得

(42)

由引理6，可得，當(dāng)k→時，ζk→0。

下面給出算法1的局部二次收斂性。

定理3設(shè)假設(shè)1成立，若所有的V∈?H(z*)都是非奇異的，對于任意的x∈Rn函數(shù)F′(x)Lipschitz連續(xù)，那么，由算法1生成的序列{zk}二次收斂于VI(X,F)的解z*=(0,x*,y*,s*)，即||zk+1-z*||=O(||zk-z*||2)。

證明類似于文獻[13]的定理5.2。

4 結(jié)語

討論了一類變分不等式問題，基于Fischer-Burmeister函數(shù)，建立了求解變分不等式問題的非單調(diào)Broyden-like算法，并證明的算法的全局收斂性以及局部超線性/二次收斂性。