非单调型变分不等式问题的新双投影算法

漆林军，何诣然

（四川师范大学数学科学学院，四川成都610066）

本文考虑经典变分不等式问题：求x*∈K，使得对所有的x∈K都满足

其中，F：Rn→Rn是连续映射，K是Rn的一个非空闭凸子集，〈·，·〉和‖·‖是欧氏内积和欧氏范数.记问题（1）和其解集分别为 VIP（F，K）和 S.变分不等式问题在工业、经济、管理学等领域都有极其重要的作用，投影算法作为求解变分不等式问题的简洁算法之一，吸引了众多学者的研究.最早的投影算法来源于 Goldstein[1]和 Levitin 等[2]对盒子约束极小化问题的梯度投影算法，借助于巴拿赫不动点定理（参见文献[3]中定理2.1.21），在假设变分不等式问题（1）中的映射F是强单调和Lipschitz连续的条件下，建立了算法的全局收敛性；之后，Korpelevich[4]提出了一种外梯度算法，在每次迭代过程中计算2次投影，将强单调假设条件削弱到了伪单调；再后来，Iusem等[5]引入 Armijo型线性搜索去掉了Lipschitz连续假设条件，双投影算法的标准假设变成了映射F是连续和伪单调的，详细发展过程与具体情况参见文献[3，6].最近，Ye 等[7]在对偶变分不等式有解的条件下，提出了一类投影算法，该算法不假设任何的单调性条件.所谓的对偶变分不等式问题是：求x*∈K，使得对所有的x∈K都满足

记问题（2）及其解集分别为 DVIP（F，K）和 SD.本文通过选取不同的超平面提出了新的算法.数值实验表明新的算法依然有效；更进一步，数值实验还表明对于一些实际问题，某些新超平面的算法比文献[7]中的算法收敛更快.

1 预备知识

引理1.1[7]若F是连续的且K是非空凸的，则SD⊂S.

定义1.1设 X⊂Rn是一个非空闭凸集.表示向量 z到K的距离，ΠK（z）表示向量 z在 K 上的投影，即 ΠK（z）满足

引理1.2[8]设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上是强单调的，c是F在K上的强单调系数；

2）〈F（y）-F（x），y-x〉≥0，则称 F 在 K 上是单调的；

3）〈F（x），y-x〉≥0 蕴含〈F（y），y-x〉≥0，则称F在K上是伪单调的；

4）‖F（y）-F（x）‖≤c‖y-x‖，则称 F 在 K上是Lipschitz连续的，c是 F在 K上的 Lipschitz常数.

引理1.5[9]设K⊂Rn是一个非空闭凸集，φ是Rn上的实值函数，记

若A非空并且φ在K上θ-Lipschitz连续（θ＞0），则对任意x∈K，以下不等式成立：

2 双投影算法

首先给出新的双投影算法.

算法2.1

步骤1 选取初始点x0∈K和参变量.取 i=0，K-1=K.

步骤2 计算 rμ（xi）.若 rμ（xi）=0，则停止；否则，转到下一步.

步骤3 寻找最小的非负整数mi使得

计算 ηi=γmi，yi=xi- ηirμ（xi），选取参数并转到下一步.

步骤4 计算xi+1=ΠKi（xi），其中

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

在后文中，总假设以下2个条件成立：

（A1）F：Rn→Rn是连续的；

（A2）SD≠∅.

下面说明算法2.1是有意义的.

性质2.1对每一个i∈N，步骤3总可以找到一个有限的非负整数mi.

证明若存在某个i0∈N使得对所有整数m都有

由假设（A1）和内积的连续性，令m→∞得到

但注意到σ＞0与步骤2中rμ（xi0）≠0，这是不可能发生的.

性质2.2设hi是算法2.1中定义的函数，对所有的i∈N，都有

和SD∈Hi成立.

证明一方面，由ηi的定义有

那么

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

而 xi∈K，因此

再由引理1.2有

由（9）和（10）式可知

又由于

有

因此

性质2.3对任意i∈N，Ki是一个非空闭凸集.更进一步，步骤4是良定的.

证明对任意i∈N，Ki是闭凸集K和有限个超平面Hj，j=0，1，…，i-1 的交集，因此也为闭凸集.又由性质2.2知对所有i∈N，SD⊆Ki.故当假设（A2）满足时，对所有的i∈N，Ki也是非空的.

3 收敛性分析

若｛xi｝i∈N是由算法2.1所产生的有限序列，则存在 i0∈N，使得 rμ（xi0）=0 或 rμ（yi0）=0，由引理1.3，xi0或 yi0为变分不等式（1）的一个解，故后文均假设｛xi｝i∈N是由算法2.1所产生的无穷序列.

定理3.1若｛xi｝i∈N是由算法2.1所产生的无穷序列，则对任意，序列是一个收敛序列.

证明由于｛xi｝i∈N是由算法2.1所产生的无穷序列，则对任意 i∈N，rμ（xi）≠0.由算法 2.1 步骤 4，xi+1=ΠKi（xi）和引理1.2，对任意

有

因此

定理3.2若｛xi｝i∈N是由算法2.1所产生的无穷序列，则序列｛xi｝i∈N、｛yi｝i∈N、｛rμ（xi）｝i∈N和｛αirμ（xi）+F（yi）｝i∈N均有界.

证明由定理3.1，可知｛xi｝i∈N有界.然后由投影的连续性与假设（A1），可得｛yi｝i∈N、｛rμ（xi）｝i∈N和｛αirμ（xi）+F（yi）｝i∈N亦有界.

定理3.3若｛xi｝i∈N是由算法2.1所产生的无穷序列，则

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

不难检验，hi是M-Lipschitz连续的.由引理1.5和性质2.2有

又由定理3.1有

因此

定理3.4若｛xi｝i∈N是由算法2.1所产生的无穷序列，则｛xi｝i∈N存在一个收敛到变分不等式（1）的解的子序列.

证明 由定理3.3有

下面分2种情况讨论：

由定理3.2，｛rμ（xi）｝i∈N有界，故存在｛xi｝i∈N的某一聚点满足

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

由定理3.2，｛rμ（xi）｝i∈N有界.设是｛xi｝i∈N的任一聚点，则存在｛xi｝i∈N的子序列｛xij｝ij∈N收敛到.由算法2.1和（1）式有

令 j→∞ ，有

定理3.5若｛xi｝i∈N是由算法2.1所产生的无穷序列，则｛xi｝i∈N收敛到变分不等式（1）的一个解.

证明若｛xi｝i∈N是由算法2.1所产生的序列是无穷序列，则由定理3.4，｛xi｝i∈N存在一个聚点是变分不等式（1）的解.设l为任意非负整数，由算法2.1有

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

4 数值实验

这一节用几个数值实验来测试不同超平面下的算法2.1，由于当α=0，μ=0时，算法2.1退化为文献[7]中的算法，因此，不仅验证了算法2.1的有效性，还将其与文献[7]的算法进行了比较.使用的工具是包含7.5版本凸优化工具箱的9.1.0.441655版本的MATLAB R2016b和X550CC华硕笔记本（CPU：intel i5-3337U）.选取10-4作为停机准则，即当 ‖r（x）‖≤10-4时，程序终止.其中的参数altern代表程序循环次数；nf代表映射F的赋值次数；time代表程序的CPU运行时间，单位是s；其余的参数均来自于算法2.1.当空间维数较高时，不同超平面的算法运行下的解的维数较高，并且其分量不同，为了方便，将其省略.例4.1是一个拟单调变分不等式的推广，n=1时是一个经典的拟单调变分不等式，在文献[7，10]中被使用过，这里测试了n=20的情形；例4.2是一个仿射变分不等式，在文献[9，11]中被使用过；例4.3是常用的Nash-Cournot NCP，Harker[13]给出的定义并进行了测试，文献[9，14-15]也用其进行了测试.

例4.1设变分不等式（1）中

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

其中，

令 n=20，选取初始点x0=（0.1，0.1，…，0.1），然后在不同的超平面下对算法2.1进行测试，结果如表1.

表1 算法2.1的数值实验结果（例4.1）Tab.1 The numerical experiment results of algorithm 2.1（Example 4.1）

例4.2当变分不等式（1）中 K=[0，1]n和F（x）=Mx+d时，其中

VI（F，K）是一个仿射单调变分不等式.选取初始点x0=（1，1，…，1）T，然后分别在 n=5 和 n=20 和不同的超平面下对算法2.1进行了测试，结果如表2和表3.

表2 算法2.1的数值实验结果（例4.2，n=5）Tab.2 The numerical experiment results of algorithm 2.1（Example 4.2 for n=5）

表3 算法2.1的数值实验结果（例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]的定义，文献[9，14-15]也对其进行了测试.当n=5 时，选取初始点 x0=（1，1，1，1，1）T对不同超平面下的算法2.1进行了测试，结果如表4.

表4 算法2.1的数值实验结果（例4.3）Tab.4 The numerical experiment results of algorithm 2.1（Example 4.3）

上面几个数值实验不仅表明算法2.1是有效的，还表明对于一些实际问题，某些新超平面的算法比文献[7]中的算法收敛更快.最后，值得思考的是，借助深度学习等技术去寻找最优的超平面.