ABSTRACT

In this paper, we present a projection and contraction algorithm for solving the quasi-variational inequality problem. The algorithm includes prediction step and correction step. The calculation of the correction step does not need to do the projection. Our method is proven to be globally convergent under certain assumptions.

Keywords:Quasi-Variational Inequality, Projection, Hyperplane

拟变分不等式问题的一种投影收缩算法

张文伟¹，张善美²，屈彪¹

¹曲阜师范大学管理学院，山东 日照

²曲阜师范大学日照校区图书馆，山东 日照

收稿日期：2016年5月2日；录用日期：2016年5月20日；发布日期：2016年5月24日

摘 要

本文给出了求解拟变分不等式问题的一种投影收缩算法，算法包括预测步和修正步，修正步的计算不需要做投影，在适当的假设条件下，证明了算法的全局收敛性。

关键词 :拟变分不等式，投影，超平面

1. 引言

给定一个向量值函数，是上的非空闭凸集，是一个集值映射且其值为非空闭凸集，拟变分不等式问题 [1] (Quasi-variational inequality problem，简记QVIP)就是求一个向量，使得，且满足

(1.1)

其中表示中所有子集所形成的集合，表示中的内积。

拟变分不等式问题在经济平衡理论、最优控制论、对策论、交通模型以及社会和经济模型等许多方面都有着广泛的应用。经济问题中的广义Nash均衡问题可以等价地转化为一个拟变分不等式问题 [2] 。研究拟变分不等式问题的有效数值解法有着重要的理论意义和实用价值。

当时，拟变分不等式问题就退化为了变分不等式问题，对于变分不等式问题有很多经典的算法，在文献 [3] - [5] 中都提出了两步投影法，两步投影法不仅迭代更快，而且对函数的要求也更低，而后文献 [6] 将两步投影法引入到了拟变分不等式问题的算法中，算法在每次迭代时需要计算预测步和修正步；文献 [7] 在假设算子具有协强制性条件下，对 [6] 中的算法做了改进，并给出了收敛性分析。文献 [1] 也给出了一种基于新的下降方向的投影类算法。在上述已有的二次投影类算法中，在计算预测步和修正步都需要做投影，当往可行集上的投影不易计算时会影响算法的计算效率。文献 [8] 在设计变分不等式的算法时引入了超平面，利用当前迭代点向所构造的该超平面与可行集的交做投影来产生新的迭代点，这样会使投影计算相对容易。受文献 [8] 的启发，我们将超平面引入到了拟变分不等式的算法中，设计了求解拟变分不等式问题的一种投影算法，而且算法在计算修正步时不需要做投影，最后的数值实验结果可以说明这样改进的算法是可行有效的。

2. 预备知识

本节中，我们将给出算法及证明中所用到的定义、引理、假设条件等。

对于给定的非空闭凸集，从点到的正交投影(以下我们简称投影)定义为：

它有如下性质：

引理2.1 [9] ：设集合为非空闭凸集，则对,有下列不等式成立：

(1)；

(2)；

(3)。

由引理2.1之(1)知，投影算子具有非扩张性，即：对任意的，有

引理2.2 [8] ：设集合为非空闭凸集，是上的Lipschitz连续实函数，。若Lipschitz连续系数，则对任意，有：

令为的映射，对任意的和，定义：

,

引理2.3 [1] ：对任意给定的向量和映射有：

(a) 当时，关于是单调增函数；

(b) 当时，关于是单调减函数。

引理2.4：为的连续映射，对任意的和，我们有：

引理2.5：若，则对任意的，有

证：

定义2.1 [1] ：令则映射称

(1) 在处上半连续，若

；

(2) 在处下半连续，若对任意满足的点列，,及满足，均存在一点列，使得且成立；

(3) 在处连续，若在处既上半连续，又下半连续；

(4) 在集合上连续，当且仅当在上的每一点都连续。

定义2.2：称映射在上是伪单调的，若对任意的有：

定义2.3：，称映射在处是严格单调的，若对任意的且有：

定义2.4 [7] ：映射称为在上是Lipschitz连续的，如果存在常数，使得：

,

在本文中我们做如下假设：

假设(H)

(a)。这里，其中， .

(b)在上连续；

(c) 函数是伪单调的。

注：尽管假设(a)比拟变分不等式解集非空的假设更强，而且不容易验证它是否成立，但它保证了QVIP的解集是非空的。此假设首次出现在文献 [6] ，而后在文献 [1] [7] 中也多次使用。

3. 算法及其收敛性分析

算法3.1

步骤0：给定常数，选取参数，，，置，选定任意的初始点令。

步骤1：根据当前迭代点，计算

如果，停止。否则，转到步骤2。

步骤2：求，为使得下面不等式成立的最小非负整数，

，

其中，。

步骤3：计算

其中：

令：

步骤4：让，回到步骤1。

注：在第3步中这样定义是由于在算法中，是通过将向集合投影得到的，即：

当令，时，如果向的投影在集合中，此时为向集合的投影，否则向集合的投影点为两集合交集中的点。

在算法中选用的超平面是。

下面说明该算法的合理性：

引理3.1：对任意的向量，定义。则对任意的，当是一个充分小的正数时，我们有：

(3.1)

证明：我们知道当时.

如果存在一个使得，由引理2.1(2) 我们可以得到对任意的都成立，此时(3.1)对任意的都成立。

如果对所有的都成立，现假设(3.1)不成立，即存在一个正实数序列趋于0，使得对任意的有：

利用Cauchy-Schwartz不等式可得到：

(3.2)

下面考虑两种情况：

(1)：,则当时会趋于0，而会趋于一个正数，这与(3.2)矛盾。

(2)：，这时有，因为是连续的并且当时，，会趋于0，而利用引理2.3(b)，当时不会小于正数，这与(3.2)矛盾。

引理3.2：设在上连续且在上伪单调，是算法3.1生成的无穷数列，则对任意的，有，。

证明：由和的定义可知利用的伪单调性有：

进而有如下不等式：

其中第一个不等式由及引理2.1(2)可得。

注：由引理3.2知，能够严格分离当前迭代点和集合。

在下面的收敛性证明中，为了方便论述，我们使用的第二种表示方法即：，同时令：。

定理3.1：设在上连续且假设H成立，是算法3.1生成的无穷数列，则的任何聚点是QVIP(1.1)的一个解。

证明 取，根据引理2.5我们得到：

有引理3.2知，所以，进而。由此可知数列是严格单调递减且有下界的数列，从而是收敛数列。由此可知是有界序列，且：

(3.3)

再由是上的连续映射，所以序列是有界的，由投影算子的非扩张性易知也是有界的。因此存在使得

这就意味着对任意的，函数都是连续的。注意到，由引理2.2可得

,

则结合引理3.2有：

因此式(3.3)意味着：

(3.4)

假设是的一个聚点，则必存在收敛子列，使得：

，

这里。下面我们来证明是(1.1)的一个解。

首先证明。由(3.4)式得：

再由及的上半连续性，即得：。

下面我们来证明：。为此我们先证存在的一个子列其中，使得

其中。

下面考虑两种情况：

(1)：，由引理2.4，我们有：

结合式(3.4)有：

(2)：，因为，所以存在子列，使得，因此对充分小的，一定违背了步骤2中的约束规则，即：

利用Cauchy-Schwartz不等式和引理2.4，我们有：

即：

而且：

所以有：

因此，我们有：

由于是下半连续的，那么，对，存在一个序列，，使得。

由可得：

(3.5)

可得：

当两边取极限，由于和的有界性，我们得到

由的任意性，得到了我们所要证明的结论。

4. 数值实验

为了验证算法的可行性和有效性，我们通过MATLAB用算法3.1解决了一个由广义纳什均衡问题转化成的拟变分不等式问题。在计算过程中，参数选取为：，，，。在下面的数值结果中，近似解指最后一个迭代点，最大迭代步数限定为1000步。

例1：此例是一个广义纳什均衡问题，首次被Harker和Outrata [10] 在1991年提出，该问题是一个两人对策，每个人选取0到10之间的一个数，并且它们的和不能超过15。费用函数和映射定义如下：

现在考虑此问题的形式，函数定义为：

,

它的解组成如下：点及线段。从不同的初始点出发，用算法3.1得到的数值结果如表1所示。

例2：此例是在例1的基础上，将集值映射替换为：。

得到的数值结果如表2所示。

表1. 例1的数值结果

表2. 例2的数值结果

从表1可以看出，从不同的初始点出发，用算法3.1都能得到原问题的解。

从表2可以看出，算法3.1在例2中从不同的初始点出发都能正确的给出拟变分不等式解。

基金项目

本文为国家自然科学基金（11271226）和山东省优秀中青年科学家科研奖励基金(BS2012SF027)资助项目。

文章引用

张文伟,张善美,屈 彪. 拟变分不等式问题的一种投影收缩算法
A Projection and Contraction Algorithm for Quasi-Variational Inequality Problem[J]. 运筹与模糊学, 2016, 06(02): 51-59. http://dx.doi.org/10.12677/ORF.2016.62007

参考文献 (References)