廣義混合變分不等式的weak-sharp解及算法的有限收斂

余 靜， 夏福全

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

本文總假設(shè)Rn為歐式空間，〈·，·〉和‖·‖分別表示Rn的標(biāo)準(zhǔn)內(nèi)積和l2范數(shù).

設(shè)W?Rn是非空閉凸子集，θ：Rn→R∪｛＋∞｝是下半連續(xù)凸函數(shù)，F(xiàn)：Rn→2Rn是集值映射.本文所研究的廣義混合變分不等式問題（簡記為 GMVIP）為：求 w*∈W，y*∈F（w*），使得

本文總假設(shè)廣義混合變分不等式問題的解集W*≠?且 dom（θ）?W，其中

當(dāng)集值映射F退化為單值映射F：Rn→Rn時，問題（1）退化為下列的一般混合變分不等式問題（簡記為 MVIP）：求 x*∈W，使得

當(dāng)θ：Rn→R∪｛＋∞｝為集合W的指示函數(shù)時，問題（1）退化為下列的廣義變分不等式問題（簡記為 GVIP）：求 x*∈W，y*∈F（x*），使得

Huang等［1］在Banach空間T中給出了一般混合變分不等式問題（2）的解集X*所滿足的weaksharp 條件：存在 α ＞0，ε∈（0，1），使得

其中，W?T是非空閉凸子集，BT*是T的對偶空間T*中的單位閉球，F(xiàn)：T→T*是單值映射，g：T→R是下半連續(xù)凸函數(shù)，對是集值映射，其定義為

TW（x*）稱為閉凸集 W在點 x*處的切錐，其定義為：

NX*（x*）稱為集合X*在點x*處的法錐，其定義為

顯然，

Huang等［1］利用與問題（2）相關(guān)的間隙函數(shù)，給出了weak-sharp條件（4）成立的等價刻畫：存在 τ＞0，使得

其中，dist（x，X*）表示點 x到解集 X*的距離，其定義為：

h（x）表示與問題（2）相關(guān)的間隙函數(shù)，其定義為：

另一方面，Xiong等［2］在Rn空間中給出了廣義變分不等式問題（3）的解集 S0所滿足的weaksharp條件：存在α＞0，使得

其中，W?Rn是非空閉凸子集，B是Rn空間中的單位閉球，G：Rn→2Rn的集值映射，其定義為：

顯然，對?x∈Rn，G（x）?F（x）.

進(jìn)一步，Xiong等［2］給出了 weak-sharp條件（5）成立的等價刻畫：存在α＞0，使得

其中，δS（z）稱為集合S的支撐函數(shù)，其定義為：

顯然

對非空子集A，B?Rn有

最后，Xiong等［2］在GVIP問題的解集 S0滿足 weak-sharp條件之下，獲得了GVIP問題的任意迭代算法有限收斂的等價條件.

雖然Huang等［1］獲得了一般混合變分不等式MVIP問題的解集X*滿足weak-sharp條件的等價刻畫，但是Huang等［1］并沒有通過 weak-sharp條件獲得MVIP問題解的任意迭代算法有限收斂的等價條件.而Xiong等［2］不僅獲得了廣義變分不等式GVIP問題的解集S0滿足weak-sharp條件的等價刻畫，同時通過GVIP解集滿足weak-sharp條件的假設(shè)之下，獲得求解GVIP問題解的任意迭代算法有限收斂的等價條件.本文將結(jié)合文獻(xiàn)［1-2］中的方法，研究廣義混合變分不等式GMVIP問題的解集W*滿足 weak-sharp條件的等價刻畫，并在GMVIP問題解集滿足weak-sharp條件的假設(shè)之下，獲得GMVIP問題解的任意迭代算法有限收斂的等價條件.最后，本文以廣義混合變分不等式GMVIP問題的超投影近似點算法為特例，在一定的條件下，獲得該算法的有限收斂性.

1 預(yù)備知識

設(shè)非空集合 D?Rn，x∈Rn，如果

則稱dist（x，D）為點 x到集合 D 的距離.如果

則稱PD（x）為點x在集合D上的投影.顯然，如果D是非空閉凸集，則PD（x）是單點集.

下面給出一個重要的投影性質(zhì)：

顯然，由（9）式有

下面給出一些定義及引理.

定義 1.1［3］設(shè) F：Rn→2Rn是集值映射，如果對任意 x，y∈Rn，u∈F（x），v∈F（y），均有

則稱集值映射F在Rn上單調(diào).

定義 1.2［4］設(shè) f：Rn→R，x∈Rn，若對任意收斂于x的點列｛xk｝?Rn均有

則稱函數(shù)f：Rn→R在x處下半連續(xù).如果函數(shù)f在Rn上每一點均下半連續(xù)，則稱f在Rn上下半連續(xù).

定義 1.3［4］設(shè) θ：Rn→R，x∈Rn，如果

則稱?θ（x）為函數(shù)θ在x處的次微分.

定義 1.4［5］設(shè)｛Ck｝k∈N是Rn的非空子集序列，則｛Ck｝k∈N的內(nèi)極限定義為

其中，N∞：＝｛N?N：N＼N 有限｝，N是自然數(shù)集表示序列按指標(biāo)集N收斂.顯然，如果Ck：＝｛xk｝，則內(nèi)極限就等同于極限.

引理1.5設(shè)W?Rn是非空閉凸子集，w∈W.則對?z∈NW（w）有

其中，TW（w）為閉凸集W在點w處的切錐.

證明由W是非空閉凸子集，可知TW（w）是非空閉凸錐且 NW（w）＝［TW（w）］?.由 z∈NW（w），有 z∈［TW（w）］?，則對?y∈TW（w），有〈z，y〉≤0.因此 PTW（w）（z）＝0.

顯然問題（1）等價于：求w*∈W，使得

由（11）式可知，存在 y*∈F（w*），z*∈?θ（w*），使得

由（12）式及引理1.5 可知

引理 1.6［4］設(shè) Ai?Rn（i＝1，2，…，m）是非空閉凸錐，則

引理 1.7［6］設(shè) A?Rn，B?Rn，A、B 均為非空閉凸子集.則A?B當(dāng)且僅當(dāng)

引理 1.8［2］設(shè) W?Rn是非空閉凸子集.w∈W，y∈Rn.則

2 廣義混合變分不等式問題解的Weaksharp條件

首先本文給出GMVIP問題的解集W*滿足的weak-sharp條件：存在α＞0，使得

其中，映射G由（6）式定義.

如果GMVIP問題（1）中的集值映射F退化為單值映射 F：Rn→Rn，則 GMVIP 問題（1）就退化為MVIP問題.此時，weak-sharp條件（1）就退化為weak-sharp條件（4）.如果 GMVIP 問題（1）中的函數(shù)θ退化為集合W的指示函數(shù)，則GMVIP問題（1）就退化為GVIP問題.此時，weak-sharp條件（14）就退化為weak-sharp條件（5）.

首先給出下列命題.

命題2.1下面等式恒成立：

（i）［TW（w*）∩NW*（w*）］?＝cl conv（NW（w*）∪TW*（w*））；

（ii）對?z∈Rn有

證明（i）由 W?Rn是非空閉凸集，可知TW（w*）是非空閉凸錐.而 NW*（w*）也是非空閉凸錐，則

由引理1.6可知結(jié)論成立.

（ii）設(shè) z∈Rn，則

其中，上式中的第一個等式是由（i）獲得，第二個等式是由（7）式獲得，第三個等式是由（8）式獲得.

命題 2.2［2］設(shè) W?Rn是非空閉凸子集，F(xiàn)：Rn→2Rn是集值映射，G：Rn→2Rn是集值映射，則

（i）如果F在W上極大單調(diào)，則G在W*上是凸值；

（ii）如果F在W上是緊值，則G在W*上是緊值.

下面給出問題（1）的解集W*滿足（14）式的一個等價條件.

定理2.3設(shè)G在W*上是緊凸值，則問題（1）的解集W*滿足weak-sharp條件當(dāng)且僅當(dāng)存在α＞0，使得

證明設(shè)G在W*上是緊凸值，w*∈W*，則G（w*）是緊凸集.顯然，αB 是緊凸集，?θ（w*）是閉凸集，又由［TW（w*）∩NW*（w*）］?是閉凸集可知G（w*）＋?θ（w*）＋［TW（w*）∩NW*（w*）］?是閉凸集.設(shè)解集W*滿足weak-sharp條件，則由（14）式可知，存在α＞0，使得對?w*∈W*有

因此，對?z∈Rn有

式中的第一個不等式是由W*滿足（17）式及引理1.7 獲得，最后一個等式是由命題 2.1 中的（ii）獲得.若存在 α ＞0，對?w*∈W*，?z∈Rn，有（16）式成立.則由（18）式可得

由（19）式及引理1.7 可得

3 廣義混合變分不等式問題的迭代算法有限收斂的等價條件

下面將在GMVIP問題（1）解集滿足weaksharp條件的假設(shè)之下，獲得GMVIP問題（1）解的任意迭代算法有限收斂的等價條件.

定理 3.1設(shè) W?Rn是非空閉凸子集，｛wk｝?W.F：Rn→2Rn是集值映射，θ：Rn→R∪｛＋ ∞ ｝為真凸下半連續(xù)函數(shù).若對于充分大的k，wk∈W*，則存在 yk∈F（wk），zk∈?θ（wk），使得

證明設(shè)存在 k0＞0，當(dāng) k≥k0時，有 wk∈W*.則當(dāng) k≥k0時，由（11）式有

由（21）式可知，存在 yk∈F（wk），zk∈?θ（wk），使得

由（22）式及引理1.5 有

因此，（20）式成立.

定理3.2設(shè) W?Rn是非空閉凸子集.F：Rn→2Rn是單調(diào)集值映射，θ：Rn→R∪｛＋ ∞ ｝為真凸下半連續(xù)函數(shù).問題（1）的解集W*是非空閉凸子集且滿足（14）式.｛wk｝?W是任意迭代算法產(chǎn)生的序列.則對于充分大的k，wk∈W*當(dāng)且僅當(dāng)

其中，

證明設(shè)存在 k0＞0，當(dāng) k≥k0時，有 wk∈W*.則當(dāng) k≥k0時，由（11）式可得

由（24）式可知，存在 yk∈F（wk），zk∈?θ（wk），使得

由（25）式及引理1.5 可知，當(dāng) k≥k0時，有

令 N：＝｛k0＋1，k0＋2，…｝，顯然 N∈N∞，又

及

由（27）和（28）式可得

設(shè)（23）式成立.假設(shè)對?K∈N，存在 k≥K，使得 wk≥W*.也即存在序列｛wk｝k∈K?｛wk｝，K?N，使得wk≥W*.由（23）式可知，存在 N∈N∞，yk∈F（wk），zk∈?θ（wk），k∈N 使得

令 Z＝K∩N，由（29）式有

由W*是非空閉凸子集，則對?wk（k∈Z），存在唯一 uk∈W*，使得

由（31）式可得

則對?k∈Z，有

及

由W*滿足（14）式，則存在α＞0，使得對?k∈Z有

使得

因此，對?k∈Z有

式中的第二個等式是由（35）式獲得，第一個不等式是由（32）式及

獲得，第二個不等式是由F的單調(diào)性及?θ的單調(diào)性獲得，最后一個不等式是由（33）式及

獲得，最后一個等式是由引理1.8獲得.由于

因此，由（36）式可得 α≤0，與 α ＞0矛盾.故結(jié)論成立.

如果GMVIP問題（1）中的集值映射F退化為單值映射 F：Rn→Rn，則 GMVIP 問題（1）就退化為MVIP問題.由（4）式可知，MVIP問題的解集W*滿足的weak-sharp條件為：

從而，由定理3.2可得如下推論：

推論 3.3設(shè) W?Rn是非空閉凸子集.F：Rn→Rn是單調(diào)單值映射，θ：Rn→R∪｛＋∞｝為真凸下半連續(xù)函數(shù).MVIP問題的解集W*是非空閉凸子集且滿足（37）式.｛wk｝?W是任意迭代算法產(chǎn)生的序列.則對于充分大的k，wk∈W*當(dāng)且僅當(dāng)

其中

3.1 超投影近似點算法的有限收斂顯然問題（1）等價于：求 w*∈W，使得

令

則問題（1）等價于：求 w*∈W，使得

接下來，本文將根據(jù)Solodov等［7］提出的求解極大單調(diào)包含問題（41）的超投影近似點算法，給出求解GMVIP 問題（1）的超投影近似點算法 3.1.1，并運用定理3.2證明此算法在滿足一定條件下有限收斂.

算法 3.1.1第一步：任給 z0∈Rn，σ∈［0，1），得到 zk.

第二步：任給 μk＞0，求 wk∈Rn，使得

其中，mk∈F（wk），hk∈NW（wk），rk∈?θ（wk），εk滿足

第三步：如果 mk＋hk＋rk＝0或 wk＝zk，停止迭代.否則

第四步：令k＝k＋1，回到第二步.

對于算法3.1.1，假設(shè)下面的條件成立：

（i）W*≠?；

（ii）F：Rn→2Rn為極大單調(diào)映射；

（iii）W?dom F，ri（dom F）∩ri（W）∩W*≠?.假設(shè)（i）～（iii）保證了映射 A＝F ＋NW＋?θ是極大單調(diào)的.

定理 3.1.2［7］設(shè)｛zk｝是由算法 3.1.1 獲得的序列，則

（a）｛zk｝有界；

（b）若參數(shù)序列｛μk｝滿足 μk≤μ ＜ ∞，?k＝0，1，2，…，則收斂到W*中的點.

定理 3.1.3設(shè) W?Rn是非空閉凸子集，θ：Rn→R∪｛＋∞｝為真凸下半連續(xù)函數(shù).GMVIP問題的解集 W*是非空閉凸子集且滿足（14）式.｛wk｝?W 是算法 3.1.1 產(chǎn)生的序列.假設(shè)（i）～（iii）成立.則對于充分大的 k，wk∈W*.

證明由定理 3.1.2的（b）可知，存在≥z∈W*，使得

由（a）可知

則存在N∈N∞使得

由 W 是非空閉凸集，則對?k∈N，TW（wk），NW（wk）均為非空閉凸錐.由 Moreau分解定理，對mk∈F（wk），rk∈?θ（wk）有

因此，對 hk∈NW（wk）（k∈N）及（45）式，有

由（44）和（46）式可得

又

因此，由定義1.4可得

由定理3.2可知結(jié)論成立.