漆林軍，何詣然

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

本文考慮經(jīng)典變分不等式問題：求x*∈K，使得對所有的x∈K都滿足

其中，F(xiàn)：Rn→Rn是連續(xù)映射，K是Rn的一個非空閉凸子集，〈·，·〉和‖·‖是歐氏內(nèi)積和歐氏范數(shù).記問題（1）和其解集分別為 VIP（F，K）和 S.變分不等式問題在工業(yè)、經(jīng)濟(jì)、管理學(xué)等領(lǐng)域都有極其重要的作用，投影算法作為求解變分不等式問題的簡潔算法之一，吸引了眾多學(xué)者的研究.最早的投影算法來源于 Goldstein[1]和 Levitin 等[2]對盒子約束極小化問題的梯度投影算法，借助于巴拿赫不動點(diǎn)定理（參見文獻(xiàn)[3]中定理2.1.21），在假設(shè)變分不等式問題（1）中的映射F是強(qiáng)單調(diào)和Lipschitz連續(xù)的條件下，建立了算法的全局收斂性；之后，Korpelevich[4]提出了一種外梯度算法，在每次迭代過程中計算2次投影，將強(qiáng)單調(diào)假設(shè)條件削弱到了偽單調(diào)；再后來，Iusem等[5]引入 Armijo型線性搜索去掉了Lipschitz連續(xù)假設(shè)條件，雙投影算法的標(biāo)準(zhǔn)假設(shè)變成了映射F是連續(xù)和偽單調(diào)的，詳細(xì)發(fā)展過程與具體情況參見文獻(xiàn)[3，6].最近，Ye 等[7]在對偶變分不等式有解的條件下，提出了一類投影算法，該算法不假設(shè)任何的單調(diào)性條件.所謂的對偶變分不等式問題是：求x*∈K，使得對所有的x∈K都滿足

記問題（2）及其解集分別為 DVIP（F，K）和 SD.本文通過選取不同的超平面提出了新的算法.數(shù)值實驗表明新的算法依然有效；更進(jìn)一步，數(shù)值實驗還表明對于一些實際問題，某些新超平面的算法比文獻(xiàn)[7]中的算法收斂更快.

1 預(yù)備知識

引理1.1[7]若F是連續(xù)的且K是非空凸的，則SD?S.

定義1.1設(shè) X?Rn是一個非空閉凸集.表示向量 z到K的距離，ΠK（z）表示向量 z在 K 上的投影，即 ΠK（z）滿足

引理1.2[8]設(shè)K?Rn是一個非空閉凸集，x0∈Rn，以下不等式成立：

為了方便以后知識的引入，記

引理1.3[3]若μ＞0，則以下2個命題等價：

（a）x∈S；

（b）‖rμ（x）‖ =0.

引理1.4[9]若 x∈K ，μ ＞0，則以下不等式成立：

定義1.2映射 F：K?Rn→Rn，任意 x，y∈K，c＞0，若

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

2）〈F（y）-F（x），y-x〉≥0，則稱 F 在 K 上是單調(diào)的；

3）〈F（x），y-x〉≥0 蘊(yùn)含〈F（y），y-x〉≥0，則稱F在K上是偽單調(diào)的；

4）‖F(xiàn)（y）-F（x）‖≤c‖y-x‖，則稱 F 在 K上是Lipschitz連續(xù)的，c是 F在 K上的 Lipschitz常數(shù).

引理1.5[9]設(shè)K?Rn是一個非空閉凸集，φ是Rn上的實值函數(shù)，記

若A非空并且φ在K上θ-Lipschitz連續(xù)（θ＞0），則對任意x∈K，以下不等式成立：

2 雙投影算法

首先給出新的雙投影算法.

算法2.1

步驟1 選取初始點(diǎn)x0∈K和參變量.取 i=0，K-1=K.

步驟2 計算 rμ（xi）.若 rμ（xi）=0，則停止；否則，轉(zhuǎn)到下一步.

步驟3 尋找最小的非負(fù)整數(shù)mi使得

計算 ηi=γmi，yi=xi- ηirμ（xi），選取參數(shù)并轉(zhuǎn)到下一步.

步驟4 計算xi+1=ΠKi（xi），其中

令i=i+1，回到步驟2.

在后文中，總假設(shè)以下2個條件成立：

（A1）F：Rn→Rn是連續(xù)的；

（A2）SD≠?.

下面說明算法2.1是有意義的.

性質(zhì)2.1對每一個i∈N，步驟3總可以找到一個有限的非負(fù)整數(shù)mi.

證明若存在某個i0∈N使得對所有整數(shù)m都有

由假設(shè)（A1）和內(nèi)積的連續(xù)性，令m→∞得到

但注意到σ＞0與步驟2中rμ（xi0）≠0，這是不可能發(fā)生的.

性質(zhì)2.2設(shè)hi是算法2.1中定義的函數(shù)，對所有的i∈N，都有

和SD∈Hi成立.

證明一方面，由ηi的定義有

那么

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

而 xi∈K，因此

再由引理1.2有

由（9）和（10）式可知

又由于

有

因此

性質(zhì)2.3對任意i∈N，Ki是一個非空閉凸集.更進(jìn)一步，步驟4是良定的.

證明對任意i∈N，Ki是閉凸集K和有限個超平面Hj，j=0，1，…，i-1 的交集，因此也為閉凸集.又由性質(zhì)2.2知對所有i∈N，SD?Ki.故當(dāng)假設(shè)（A2）滿足時，對所有的i∈N，Ki也是非空的.

3 收斂性分析

若｛xi｝i∈N是由算法2.1所產(chǎn)生的有限序列，則存在 i0∈N，使得 rμ（xi0）=0 或 rμ（yi0）=0，由引理1.3，xi0或 yi0為變分不等式（1）的一個解，故后文均假設(shè)｛xi｝i∈N是由算法2.1所產(chǎn)生的無窮序列.

定理3.1若｛xi｝i∈N是由算法2.1所產(chǎn)生的無窮序列，則對任意，序列是一個收斂序列.

證明由于｛xi｝i∈N是由算法2.1所產(chǎn)生的無窮序列，則對任意 i∈N，rμ（xi）≠0.由算法 2.1 步驟 4，xi+1=ΠKi（xi）和引理1.2，對任意

有

因此

定理3.2若｛xi｝i∈N是由算法2.1所產(chǎn)生的無窮序列，則序列｛xi｝i∈N、｛yi｝i∈N、｛rμ（xi）｝i∈N和｛αirμ（xi）+F（yi）｝i∈N均有界.

證明由定理3.1，可知｛xi｝i∈N有界.然后由投影的連續(xù)性與假設(shè)（A1），可得｛yi｝i∈N、｛rμ（xi）｝i∈N和｛αirμ（xi）+F（yi）｝i∈N亦有界.

定理3.3若｛xi｝i∈N是由算法2.1所產(chǎn)生的無窮序列，則

證明由定理3.2，｛αirμ（xi）+F（yi）｝i∈N有界，即存在M＞0，使得

不難檢驗，hi是M-Lipschitz連續(xù)的.由引理1.5和性質(zhì)2.2有

又由定理3.1有

因此

定理3.4若｛xi｝i∈N是由算法2.1所產(chǎn)生的無窮序列，則｛xi｝i∈N存在一個收斂到變分不等式（1）的解的子序列.

證明 由定理3.3有

下面分2種情況討論：

由定理3.2，｛rμ（xi）｝i∈N有界，故存在｛xi｝i∈N的某一聚點(diǎn)滿足

由引理1.3，｛xi｝i∈N存在一個收斂到變分不等式（1）的解的子序列.

由定理3.2，｛rμ（xi）｝i∈N有界.設(shè)是｛xi｝i∈N的任一聚點(diǎn)，則存在｛xi｝i∈N的子序列｛xij｝ij∈N收斂到.由算法2.1和（1）式有

令 j→∞ ，有

定理3.5若｛xi｝i∈N是由算法2.1所產(chǎn)生的無窮序列，則｛xi｝i∈N收斂到變分不等式（1）的一個解.

證明若｛xi｝i∈N是由算法2.1所產(chǎn)生的序列是無窮序列，則由定理3.4，｛xi｝i∈N存在一個聚點(diǎn)是變分不等式（1）的解.設(shè)l為任意非負(fù)整數(shù)，由算法2.1有

故對所有的i＞l，有xi∈Kl.又由Kl是閉的有∈Kl，即

4 數(shù)值實驗

這一節(jié)用幾個數(shù)值實驗來測試不同超平面下的算法2.1，由于當(dāng)α=0，μ=0時，算法2.1退化為文獻(xiàn)[7]中的算法，因此，不僅驗證了算法2.1的有效性，還將其與文獻(xiàn)[7]的算法進(jìn)行了比較.使用的工具是包含7.5版本凸優(yōu)化工具箱的9.1.0.441655版本的MATLAB R2016b和X550CC華碩筆記本（CPU：intel i5-3337U）.選取10-4作為停機(jī)準(zhǔn)則，即當(dāng) ‖r（x）‖≤10-4時，程序終止.其中的參數(shù)altern代表程序循環(huán)次數(shù)；nf代表映射F的賦值次數(shù)；time代表程序的CPU運(yùn)行時間，單位是s；其余的參數(shù)均來自于算法2.1.當(dāng)空間維數(shù)較高時，不同超平面的算法運(yùn)行下的解的維數(shù)較高，并且其分量不同，為了方便，將其省略.例4.1是一個擬單調(diào)變分不等式的推廣，n=1時是一個經(jīng)典的擬單調(diào)變分不等式，在文獻(xiàn)[7，10]中被使用過，這里測試了n=20的情形；例4.2是一個仿射變分不等式，在文獻(xiàn)[9，11]中被使用過；例4.3是常用的Nash-Cournot NCP，Harker[13]給出的定義并進(jìn)行了測試，文獻(xiàn)[9，14-15]也用其進(jìn)行了測試.

例4.1設(shè)變分不等式（1）中

對任意的 x=（x1，x2，…，xn）∈K，

其中，

令 n=20，選取初始點(diǎn)x0=（0.1，0.1，…，0.1），然后在不同的超平面下對算法2.1進(jìn)行測試，結(jié)果如表1.

表1 算法2.1的數(shù)值實驗結(jié)果（例4.1）Tab.1 The numerical experiment results of algorithm 2.1（Example 4.1）

例4.2當(dāng)變分不等式（1）中 K=[0，1]n和F（x）=Mx+d時，其中

VI（F，K）是一個仿射單調(diào)變分不等式.選取初始點(diǎn)x0=（1，1，…，1）T，然后分別在 n=5 和 n=20 和不同的超平面下對算法2.1進(jìn)行了測試，結(jié)果如表2和表3.

表2 算法2.1的數(shù)值實驗結(jié)果（例4.2，n=5）Tab.2 The numerical experiment results of algorithm 2.1（Example 4.2 for n=5）

表3 算法2.1的數(shù)值實驗結(jié)果（例4.2，n=20）Tab.3 The numerical experiment results of algorithm 2.1（Example 4.2 for n=20）

例4.3PM-Nash 5 問題，來源于 Harker[13]的定義，文獻(xiàn)[9，14-15]也對其進(jìn)行了測試.當(dāng)n=5 時，選取初始點(diǎn) x0=（1，1，1，1，1）T對不同超平面下的算法2.1進(jìn)行了測試，結(jié)果如表4.

表4 算法2.1的數(shù)值實驗結(jié)果（例4.3）Tab.4 The numerical experiment results of algorithm 2.1（Example 4.3）

上面幾個數(shù)值實驗不僅表明算法2.1是有效的，還表明對于一些實際問題，某些新超平面的算法比文獻(xiàn)[7]中的算法收斂更快.最后，值得思考的是，借助深度學(xué)習(xí)等技術(shù)去尋找最優(yōu)的超平面.