徐紫文

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

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

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

(1)

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

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

1 預(yù)備知識(shí)

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

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

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

(2)

式中C是Rn的一個(gè)非空閉凸集。記問(wèn)題(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是一個(gè)非空閉凸集，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是一個(gè)非空閉凸集，T是Rn上的實(shí)值函數(shù)，記H：={x∈C|T(x)≤0}。若H非空并且T在C上θ-Lipschitz連續(xù)(θ>0)，則對(duì)任意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)。計(jì)算

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

步驟1計(jì)算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)

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

(4)

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

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

下面說(shuō)明算法是有意義的。

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

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

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

(5)

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

(6)

即

(7)

其中，第1個(gè)不等式由步驟2得到，第2個(gè)不等式由引理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)的一個(gè)解，否則產(chǎn)生的序列為無(wú)窮序列。接下來(lái)的討論中均假設(shè)序列{xk}是由算法1所產(chǎn)生的無(wú)窮序列。

證明由于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)生的無(wú)窮序列{xk}收斂到變分不等式(1)的一個(gè)解。

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

(19)

由式(17)得

(20)

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

(21)

接下來(lái)分2種情況討論：

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

(22)

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

(23)

4 數(shù)值實(shí)驗(yàn)

本章用2個(gè)數(shù)值實(shí)驗(yàn)來(lái)測(cè)試算法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個(gè)典型例子來(lái)說(shuō)明算法的有效性。選取10-4作為停機(jī)準(zhǔn)則，即當(dāng)‖r(x)‖≤10-4時(shí)，程序終止。參數(shù)均來(lái)自于算法1且某些參數(shù)的選取與文獻(xiàn)[16]一樣，即仍選取σ=0.99，γ=0.4，另外μ=1。本文參數(shù)μ的其他取值結(jié)果以及當(dāng)空間維數(shù)較高時(shí)的解，為了方便，將其省略。用以下2個(gè)典型例子說(shuō)明算法1的有效性。例1是一個(gè)擬單調(diào)變分不等式的推廣，例2是一個(gè)仿射變分不等式。

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

表1 算法1測(cè)試-1

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

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

表2 算法1測(cè)試-2

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