非單調(diào)變分不等式問題的雙投影算法研究

徐紫文

(四川師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，四川 成都 610068)

考慮經(jīng)典變分不等式問題：求x*∈C，使得對任意x∈C，都有以下不等式成立，

〈F(x*)，x-x*〉≥0。

(1)

式中F：Rn→Rn是連續(xù)映射，C是Rn上的一個非空閉凸子集，用SOL(C，F(xiàn))表示變分不等式VI(C，F(xiàn))的解集，簡記為S，〈·，·〉是歐氏內(nèi)積。變分不等式問題是優(yōu)化理論中重要分支，并在工業(yè)、經(jīng)濟(jì)、管理學(xué)、網(wǎng)絡(luò)運(yùn)輸及交通運(yùn)輸?shù)阮I(lǐng)域都有極其重要的地位[1-4]。投影算法作為求解變分不等式問題的重要算法之一，吸引了眾多學(xué)者的關(guān)注和研究[5-7]。最經(jīng)典的變分不等式在20世紀(jì)60年代由Hartman-Stampacchia[8]提出。投影算法最初源于Goldstein[9]和Levitin-Polyak[10]，在映射F是強(qiáng)單調(diào)和Lipschtz連續(xù)的條件下，建立了算法的全局收斂性。 該投影算法的假設(shè)條件太強(qiáng)，大大地限制了其適用范圍。隨后Korpelevich[11]提出了外梯度算法，此算法將映射F是強(qiáng)單調(diào)削弱為偽單調(diào)，其算法在每次迭代過程中都需計算2次投影。此算法雖然將強(qiáng)單調(diào)假設(shè)條件削弱到了偽單調(diào)，但由于其Lipschtz連續(xù)的條件依然很強(qiáng)，仍然存在很大的局限性。1997年Iusem[12]引入Armijo-type線性搜索, 將Lipschtz連續(xù)條件削弱為連續(xù)，詳細(xì)發(fā)展過程與具體情況見文獻(xiàn)[13-14]。該方法仍然對映射F單調(diào)性有所要求，使其在實際應(yīng)用中仍有局限。最近，在文獻(xiàn)[16]中，Ye M L和He Y R僅在其對偶變分不等式有解的條件下，提出一類改進(jìn)的新雙投影算法， 該算法不假設(shè)任何單調(diào)性條件，大大擴(kuò)大了其適用范圍。受其啟發(fā)，本文通過構(gòu)造投影算子的一個新的投影區(qū)域，提出一種求解非單調(diào)變分不等式的改進(jìn)的雙投影算法。 數(shù)值實驗表明新的算法有效，比文獻(xiàn)[16]中的算法收斂更快。

本文的內(nèi)容安排如下：第1章回顧一些基本定義與基本結(jié)論；第2章提出本文算法；第3章給出本文算法的全局收斂性的相關(guān)證明；第4章用數(shù)值實驗來檢驗算法的有效性。

1 預(yù)備知識

先回顧一些概念和結(jié)論，以助于后面的證明。本文后面‖·‖均指歐氏范數(shù)。

定義1變分不等式問題(1)的對偶變分不等式為：求x*∈C，使得對所有的x∈C都滿足

〈F(x)，x-x*〉≥0。

(2)

式中C是Rn的一個非空閉凸集。記問題(2)及其解集分別為DVIP(C，F(xiàn))和SD。

引理1[15]x*∈SOL(C，F(xiàn))?‖rμ(x*)‖=0，其中μ>0。

引理2[16]若F是連續(xù)的且C是非空閉凸集，則SD?S。

引理3[17]設(shè)C?Rn是一個非空閉凸集，x∈Rn，以下不等式成立：

〈x-PC(x)，y-PC(x)〉≤0，?y∈C。

定義3映射F：C?Rn→Rn，任給x，y∈C，ξ>0，L>0，若

① 〈F(y)-F(x)，y-x〉≥ξ‖y-x‖2，則稱F在C上是強(qiáng)單調(diào)的，ξ是F在C上的強(qiáng)單調(diào)系數(shù)；

② 〈F(y)-F(x)，y-x〉≥0，則稱F在C上是單調(diào)的；

③ 〈F(x)，y-x〉≥0?〈F(y)，y-x〉≥0，則稱F在C上是偽單調(diào)的；

④ ‖F(xiàn)(y)-F(x)‖≤L‖y-x‖，則稱F在C上是Lipschtz連續(xù)的，L是F在C上的Lipschtz常數(shù)。

引理4[18]若x∈C，μ>0，則〈F(xk)，rμ(xk)〉≥u-1‖rμ(xk)‖2。

引理5[18]設(shè)C?Rn是一個非空閉凸集，T是Rn上的實值函數(shù)，記H：={x∈C|T(x)≤0}。若H非空并且T在C上θ-Lipschitz連續(xù)(θ>0)，則對任意x∈C，以下不等式成立：dist(x，H)≥θ-1max{0，T(x)}。

2 改進(jìn)的雙投影算法

算法1改進(jìn)的雙投影算法。

步驟0基本參數(shù)設(shè)置：設(shè)σ>0，μ∈(0，σ-1)，γ∈(0，1)。取x0∈C為初始點(diǎn)。計算

zk=PC(xk-μF(xk))。

步驟1計算rμ(xk)=xk-zk。若rμ(xk)=0，則停止；否則，轉(zhuǎn)到下一步。

步驟2令mk為使得式(3)成立的最小正整數(shù)m，使

〈F(xk)-F(xk-γmrμ(xk))，rμ(xk)〉≤σ‖rμ(xk)‖2

(3)

成立。計算ηk=γmk，yk=xk-ηkrμ(xk)，并轉(zhuǎn)到下一步。

(4)

在以后的所有分析中，我們總假設(shè)以下2個條件成立：

(A1)F：Rn→Rn是連續(xù)的； (A2)SD≠?。

下面說明算法是有意義的。

命題1對每一個k∈N，總存在一個有限的非負(fù)整數(shù)mk使步驟2中的不等式成立。

證明若步驟2中的不等式不總是成立，則存在某個k0∈N使得對所有非負(fù)整數(shù)m都有式(5)成立：

〈F(xk0)-F(xk0-γmrμ(xk0))，rμ(xk0)〉>σ‖rμ(xk0)‖2。

(5)

對式(5)左端，當(dāng)m→∞時，有γm→0，從而(xk0-γmrμ(xk0))→xk0。由條件(A1)和內(nèi)積的連續(xù)性可得〈F(xk0)-F(xk0-γmrμ(xk0))，rμ(xk0)〉→0，即0≥σ‖rμ(xk0)‖2。又因為σ>0，故只有rμ(xk0)=0，與步驟1中rμ(xk0)≠0矛盾。

(6)

即

(7)

其中，第1個不等式由步驟2得到，第2個不等式由引理4得到。

另一方面，任取x*∈SD， 有

〈F(yk)，yk-x*〉≥0， ?yk∈C。

(8)

故有

(9)

‖rμ(xk)‖2-μ〈F(xk)，rμ(xk)〉+〈F(yk)，rμ(xk)〉≥

‖rμ(xk)‖2-μ〈F(xk)，rμ(xk)〉+〈F(xk)，rμ(xk)〉-σ‖rμ(xk)‖2=

(1-σ)‖rμ(xk)‖2+(1-μ) 〈F(xk)，rμ(xk)〉≥

(1-σ)‖rμ(xk)‖2+(1-μ)μ-1‖rμ(xk)‖2=

(10)

〈xk-zk，x*-xk〉=〈xk-μF(xk)-zk，x*-zk〉+〈μF(xk)，x*-xk〉+

〈μF(xk)-rμ(xk)，rμ(xk)〉≤

〈μF(xk)-rμ(xk)，rμ(xk)〉。

(11)

和

(12)

故目標(biāo)不等式可由式(11)與式(12)相加，再整理得到

(13)

進(jìn)一步，由式(13)得

(14)

命題3若SD≠?，則步驟3一定成立。

3 收斂性分析

在條件(A1)和(A2)成立的情況下，若序列{xk}是由算法1所產(chǎn)生的有限序列，則存在k0∈N，使得rμ(xk0)=0，故xk0為變分不等式(1)的一個解，否則產(chǎn)生的序列為無窮序列。接下來的討論中均假設(shè)序列{xk}是由算法1所產(chǎn)生的無窮序列。

證明由于xk+1=PCk(xk)，則，

(15)

即,

(16)

(17)

由F(x)和投影算子的連續(xù)性可得序列{zk}有界，進(jìn)一步序列{yk}和序列{rμ(xk)}有界。

ζ‖x-y‖<‖〈F(yk)，x-yk〉-〈F(yk)，y-yk〉‖=
‖〈F(yk)，x-y〉‖≤‖F(xiàn)(yk)‖‖x-y‖。

(18)

但‖F(xiàn)(yk)‖>ζ與序列{yk}有界矛盾。

定理2若SD≠?，則由算法1所產(chǎn)生的無窮序列{xk}收斂到變分不等式(1)的一個解。

證明根據(jù)Ck的定義，可得

(19)

由式(17)得

(20)

由引理5、命題4、定理1和式(7)知

(21)

接下來分2種情況討論：

〈F(xk)-F(xk-γmk-1rμ(xk))，rμ(xk)}>σ‖rμ(xk)‖2。

(22)

由F(x)和rμ(x)的連續(xù)性，可令式(22)k→∞，得

(23)

4 數(shù)值實驗

本章用2個數(shù)值實驗來測試算法1，并將其與參考文獻(xiàn)[16]的算法進(jìn)行比較。 使用MATLAB版本7.1.0.246(R14)Pack3，其中包含優(yōu)化工具箱3.0版本和惠普筆記本(CPU：intel i5-4200M)。 本文將以文獻(xiàn)[16]中2個典型例子來說明算法的有效性。選取10-4作為停機(jī)準(zhǔn)則，即當(dāng)‖r(x)‖≤10-4時，程序終止。參數(shù)均來自于算法1且某些參數(shù)的選取與文獻(xiàn)[16]一樣，即仍選取σ=0.99，γ=0.4，另外μ=1。本文參數(shù)μ的其他取值結(jié)果以及當(dāng)空間維數(shù)較高時的解，為了方便，將其省略。用以下2個典型例子說明算法1的有效性。例1是一個擬單調(diào)變分不等式的推廣，例2是一個仿射變分不等式。

例1設(shè)變分不等式(1)中C=[-1，1]，F(xiàn)(x)=x2。 選取不同的初始點(diǎn)， 對算法1進(jìn)行測試，結(jié)果如表1。

表1 算法1測試-1

例2令變分不等式(1)中C=[0，1]n，F(xiàn)(x)=Mx+d，其中

選取初始點(diǎn)x0=(1，1，…，1)T，然后分別在不同的維數(shù)下進(jìn)行試驗，結(jié)果見表2。

表2 算法1測試-2

上面2個數(shù)值實驗不僅表明算法1是有效的，而且表明對某些參數(shù)，算法1比文獻(xiàn)[16]中的算法收斂更快。