求解擬變分不等式的次梯度外梯度算法

田倍昕，趙 丹，葉明露

(西華師范大學 數學與信息學院，四川 南充 637009)

20世紀以來，納什均衡問題廣泛應用在經濟、政治等領域。該理論假設了每個競爭者的策略集是一個與其他競爭者無關的常值集合，廣義納什均衡問題則假設每個競爭者的策略集都取決于其他人的決策。因此，廣義納什均衡問題的這種結構更接近于競爭市場的真實情況，引起了廣大學者的關注，參見文獻[1-3]。在一定條件下，納什均衡問題等價于一個變分不等式問題，而廣義納什均衡問題則等價于一個擬變分不等式(簡稱QVI)問題。

uk=(1-bk)xk+bkPC(xk)[xk-αF(xk)],xk+1=(1-ak)xk+akPC(uk)[uk-αF(uk)],k=0,1,2,…

該算法在映射F強單調且Lipschitz連續(需要知道Lipschitz系數或者上界)，c(x)Lipschitz連續且C0是一個閉凸集時得到了全局收斂性。受文獻[6]與文獻[13]的啟發，本文在文獻[7]的基礎上提出一種新的步長，使得新算法適用于映射單調且Lipschitz系數值未知的情況，并且該算法的每次迭代只需計算一次向可行集的投影。同時在適當的假設下，得到了算法的收斂性結果。

1 基本概念

本節給出文章需要用到的基本概念以及基礎知識。設Rn為n維歐氏空間，X為Rn的非空子集。用〈·,·〉和‖·‖分別表示Rn中的內積和范數。

設F：Rn→Rn是一個單值映射，K∶Rn?Rn是一個集值映射，并且其值為一個非空閉凸集。在上述條件下，本文考慮的擬變分不等式問題如下：尋找向量u*∈X，使得u*∈K(u*)且滿足下述不等式

〈F(u*),v-u*〉≥0，?v∈K(u*)。

(1)

對上述問題而言，如果對于任意的u∈Rn都有K(u)≡K成立，問題(1)退化成經典的變分不等式問題。即找到一個向量u*∈K使得

〈F(u*),v-u*〉≥0， ?v∈K。

(2)

接下來將回顧一些定義、性質、引理及一些與其相關的結論。

定義1[13]X為Rn的非空閉凸子集，給定映射T∶Rn→Rn，稱

(1)映射T在X上是L-Lipschitz連續的，且Lipschitz系數L>0，如果

‖T(x)-T(y)‖≤L‖x-y‖, ?x,y∈X；

(3)

(2)映射T在X上是單調的，如果

〈T(x)-T(y),x-y〉≥0, ?x,y∈X。

(4)

引理1[13]設C是Rn上的非空閉凸集，對于任意的x∈Rn，都在C中存在唯一的一點，使得該點與x的距離最近，稱這個點為x在C上的投影，記作PC(x)，即

‖x-PC(x)‖≤‖x-y‖, ?y∈C。

(5)

投影映射PC∶Rn→C還滿足下式性質

〈x-PC(x),PC(x)-y〉≥0, ?x∈Rn,?y∈C。

(6)

同時，該映射PC∶Rn→C也是非擴張的，即

‖PC(x)-PC(y)‖≤‖x-y‖， ?x,y∈Rn。

(7)

通過引理1，可以得到下面的引理。

引理2 設C是Rn上的非空閉凸集，xk+1=PC(xk)，z∈C，則有下式成立

‖xk+1-z‖2≤‖xk-z‖2-‖xk+1-xk‖2。

(8)

引理3[14]設K(·)是Rn中具有非空閉凸值的集值映射，則x*∈K(x*)是擬變分不等式的一個解，當且僅當對于任何τ>0，都有x*=PK(x*)(x*-τF(x*))成立。

vk→z(k→∞)；

(d)在X上連續當且僅當它在X上的每個點都是連續的。

注1 記擬變分不等式的解集S∶={x∈X|〈F(x),y-x〉≥0,?y∈K(x)}。則由S*與S的定義可知S*?S。因此，S*≠?的假設比S≠?的假設更強。但若對于所有x∈X，都有K(x)≡K成立，即擬變分不等式問題退化為變分不等式問題，則有S*=S。此時該假設退化為S≠?。因此，假設(i)也被文獻[13-15]作為求解QVI的一個基本假設。注意到文獻[7]中假設的集值映射C必然是連續的，且其值是一個非空的閉凸集。因此，(ii)的假設條件更弱，并且該假設也被文獻[13-15]作為求解QVI的一個基本假設。

2 算 法

在這一部分，將介紹一種新的步長去求解擬變分不等式問題。

算法1

步驟1 選取兩個參數λ1>0,μ∈(0,1)，初始點x1∈X，令k=1。計算yk=PK(xk)(xk-λkF(xk))，如果yk=xk，則算法停止，否則執行步驟2。

步驟2 計算xk+1=PTk(xk-λkF(yk))，其中Tk={ω∈X∶〈xk-λkF(xk)-yk,ω-yk〉≤0}。更新

(9)

注2 如果yk=xk，根據算法1可以得到yk=PK(yk)(yk-λF(yk))，由引理3知yk為擬變分不等式的一個解。

3 收斂性分析

證明由λk+1的定義可知{λk}為一非負單調遞減數列，從而其極限存在。下面用數學歸納法來證明

(10)

若F(yk)≠F(xk)，那么由映射F的Lipschitz連續性可以得到

定理2 考慮映射F具有單調性和L-Lipschitz連續性的QVI問題。設{xk}，{yk}是由算法1生成的任意序列，x*為解集S*中的任意一點，則有下面的不等式成立：

(11)

證明由于x*為解集S*中的一點可知x*∈K(xk)，再結合引理1中(6)式可得

〈xk-λkF(xk)-yk,x*-yk〉≤0。

由半空間Tk的定義可知x*∈Tk。再結合引理2則有下式成立

‖xk+1-x*‖2≤‖xk-λkF(yk)-x*‖2-‖xk-λkF(yk)-xk+1‖2

=‖xk-x*‖2-2〈xk-x*,λkF(yk)〉-‖xk-xk+1‖2+2〈xk-xk+1,λkF(yk)〉

=‖xk-x*‖2-‖xk-xk+1‖2-2〈xk+1-x*,λkF(yk)〉

=‖xk-x*‖2-‖xk-xk+1‖2-2〈yk-x*,λkF(yk)〉-2〈xk+1-yk,λkF(yk)〉。

(12)

利用映射F單調性、x*∈S*以及λk>0的這個事實，可以得到

〈yk-x*,λkF(yk)〉=〈yk-x*,λkF(x*)〉+〈yk-x*,λk(F(yk)-F(x*))〉≥0 。

(13)

結合(12)式與(13)式可得

‖xk+1-x*‖2≤‖xk-x*‖2-‖xk-xk+1‖2-2〈xk+1-yk,λkF(yk)〉

=‖xk-x*‖2-‖xk-yk‖2-‖yk-xk+1‖2-2〈xk-yk,yk-xk+1〉-2〈xk+1-yk,λkF(yk)〉

=‖xk-x*‖2-‖xk-yk‖2-‖yk-xk+1‖2-2〈xk-λkF(xk)-yk,yk-xk+1〉-

2〈yk-xk+1,λkF(xk)〉-2〈xk+1-yk,λkF(yk)〉。

因為xk+1∈Tk，由半空間的定義可得〈xk-λkF(xk)-yk,yk-xk+1〉≥0。因此，

‖xk+1-x*‖2≤‖xk-x*‖2-‖xk-yk‖2-‖yk-xk+1‖2-2〈yk-xk+1,λkF(xk)〉-2〈xk+1-yk,λkF(yk)〉

=‖xk-x*‖2-‖xk-yk‖2-‖yk-xk+1‖2+2λk〈F(xk)-F(yk),xk+1-yk〉

≤‖xk-x*‖2-‖xk-yk‖2-‖yk-xk+1‖2+2λk‖F(xk)-F(yk)‖‖xk+1-yk‖。

(14)

下面對2λk‖F(xk)-F(yk)‖‖xk+1-yk‖的值進行分類討論：

(i)如果‖F(xk)-F(yk)‖≠0，根據λk+1的定義可得

(15)

其中第二個不等式是由a2+b2≥2ab得到的。

(ii)如果‖F(xk)-F(yk)‖=0,則(15)式也成立。

綜上所述，(15)式成立。結合(14)式與(15)式可得(11)。

定理3 如果假設1成立且{xk}為由算法1生成的無窮序列，則下述結論成立

2)序列{xk}有界，且其任一聚點都是擬變分不等式的一個解。

(16)

‖xk+1-x*‖2≤‖xk-x*‖2，k>N。

2)由1)知數列{xk}有界。設u為其任一聚點，則存在指標集I?N使得xk→u(k∈I,k→∞)。下證聚點是擬變分不等式問題(1)的解。為此，先證明u∈K(u)。由(11)式可得

(17)

(18)

進而由迫斂性可得

(19)

由此，結合不等式‖yk-yk-1‖≤‖yk-xk‖+‖xk-yk-1‖可知

(20)

由(19)式結合所設xk→u(k∈I,k→∞)可得yk→u(k∈I,k→∞)。進而結合K的上半連續性以及yk∈K(xk)的這個事實可以推出u∈K(u)。

〈yk-xk+λkF(xk),v-yk〉≥0, ?v∈K(xk),?k∈I。

(21)

特別地，對任意的k∈I有

0≤〈yk-xk+λkF(xk),vk-yk〉

=〈yk-xk,vk-yk〉+〈λkF(xk),vk-yk〉

=〈yk-xk,vk-yk〉+〈λkF(xk),vk-xk〉+〈λkF(xk),xk-yk〉。

(22)

0≤〈F(u),z-u〉, ?z∈K(u)。

上式結合u∈K(u)可知u為擬變分不等式問題(1)的解。

證明因為u是序列{xk}的聚點，故根據定理3可知

〈F(u),z-u〉≥0,?z∈K(u)。

(23)

設x*為解集S*中的一點，再結合yk∈K(xk)及S*的定義可得

〈F(x*),yk-x*〉≥0。

(24)

在(24)式中令k→∞，k∈I，再結合(19)式與u是序列{xk}的聚點的這個事實可得

〈F(x*),u-x*〉≥0。

(25)

進而，結合F的單調性可得

〈F(u),u-x*〉≥0。

(26)

由S*的定義知x*∈K(u)，從而由(23)可得

〈F(u),x*-u〉≥0 。

(27)

同理結合(27)式與F的單調性可得

〈F(x*),x*-u〉≥0 。

(28)

結合(26)式與(27)式可得〈F(u),x*-u〉=0，結合(25)式與(28)式可得〈F(x*),x*-u〉=0。

由此可得〈F(x*)-F(u),x*-u〉=0，再結合F在u點的嚴格單調性可得u=x*∈S*。

4 結 語

本文提出了一種新的步長規則來求解QVI問題，在映射單調且Lipschitz系數難以估計的情況下證明了算法的強收斂性。本文的算法相較于文獻[7]擁有更加廣泛的適用范圍。