1. 引言
本文将研究具有双约束条件的变分不等式问题:求解
使得到
(1.1)
其中
是两个映射,
是一个非空闭凸集合。
具有双约束条件的变分不等式问题出现在许多数学领域中,如下面的双人博弈问题:双约束的双人博弈问题(1.2)中可以转化为具有双约束条件的变分不等式问题(1.1)
(1.2)
其中
都为
上的映射。其中
和
对任意的
在
处是凸的,其中
和
对任意的
在
处是凸的。通过标准化函数
(1.3)
其中
,
且
。通过标准化函数问题(1.2)可以转化为如下形式。
求解
使得
(1.4)
如果问题(1.4)和目标函数是可微的,那么它就可以表示成为一个变分不等式问题
(1.5)
其中
。
具有双约束条件的变分不等式问题还出现在许多其他的数学领域中,如:价值均衡问题的最简模型、拟变分不等式问题以及双层规划问题等。具体可参见Antipin [1]。
有限维变分不等式和互补问题的理论研究和算法研究被Facchinei和Pang [2] 进行了详细的总结和介绍,该专著被认为是优化界最有价值的著作,其内容记录了在
空间中的研究变分不等式问题和互补问题的绝大部分重要成果,包括互补问题和变分不等式的稳定性分析、灵敏度分析、数值解法等。但是这本专著中没有记录变分不等式的微分方程方法。
近几年关于求解变分不等式的算法简单介绍如下:Nazemi和Sabeghi [3] [4] 应用神经网络模型有效的求解了凸二阶锥约束变分不等式问题。王莉,单峰和王诗云 [5] 通过运用增广拉格朗日法和非精确半光滑牛顿法求解了具有约束条件的变分不等式的一类子问题。米特特和方长杰 [6] 提出了一种惯性次梯度外梯度方法求解变分不等式问题。Kwelegano,Zegeye和Boikanyo [7] 研究了一种求解分裂等式变分不等式问题的近似解法。更多求解变分不等式的方法参阅文献 [8] - [13]。
在Antipin [1] 中提出了一个具有双约束条件的变分不等式。并将原变分不等式问题在一定条件下转换成鞍点问题。通过应用投影算子,建立一个微分方程系统,即微分方程系统解的聚点就是原问题的解。应用对称函数的性质,证明了微分方程解的轨迹的收敛性。但是,Antipin [1] 并没有给出具体算例说明本方法的可行性。Antipin [1] 通过建立的一阶微分方程系统来求解双约束变分不等式问题。本文将在此基础上,建立二阶的分方程系统来求解双约束变分不等式问题。
本文运用微分方程方法求解双约束变分不等式,与传统的微分方程方法或神经网络方法不同的是,我们直接从投影算子方程组建立微分方程系统,并且不必构造Lyapunov函数得到微分方程系统的解的轨迹的聚点是所研究的变分不等式问题的解。
本文内容如下:在第二节中会介绍对称函数的定义及其相关性质,这些性质在收敛定理的证明过程中会起到重要的作用;会将具有双约束条件的变分不等式问题看作一个特殊的优化问题,运用该优化问题的拉格朗日函数的鞍点不等式和投影算子得到具有双约束条件的变分不等式(1.1)的一系列等价表示;第三节,运用第二节得到的等价的投影算子方程建立具有控制过程的二阶微分方程系统,并运用对称函数的性质证明了该二阶微分方程系统的解的轨迹的收敛性;最后,运用具有控制过程的二阶微分方程系统求解了两个算例,说明了该方法的有效性。
2. 预备知识
下面对对称函数的定义和相关性质做如下介绍。
引理2.1 [14]:设H为Hilbert空间,且
是一个闭凸集合。对于给定的
满足
当且仅当
。
定义2.1 [1]:
称为是对称函数,如果满足下面的关系
(2.1)
与此同时,Antipin [1] 也给出了对称函数
的下面重要性质。
性质2.1 [1]:对称函数
在集合
上关于第一元v和第二元w的梯度矩阵是相等的,即
(2.2)
证明:在(2.1)中左边关于第二元w和右边关于第一元v求导得
其中
和
是
矩阵,在上式中令
便得到(2.2)。证毕。□
性质2.2 [1]:对称函数
在集合
上梯度
与
是相等的,即
(2.3)
证明:根据可微的定义有
(2.4)
其中
,当
。
在(2.1)中令
,则再由(2.2)和(2.3)可得
(2.5)
其中
,当
。则(2.5)是(2.4)的特殊情形,由(2.5)可以知道
可以看作是函数
当
时的函数,其梯度为
,从(2.5)可以得到(2.3)成立。证毕。□
问题(1.1)可以看作是求解下面的优化问题
(2.6)
其中
,且由(1.1)是一类变分不等式可知
,进一步
是上述优化问题(2.6)的解。
可以得到,优化问题(2.6)的拉格朗日函数
(2.7)
其中
是原问题的解,w和p分别是原始变量和对偶变量。由于
是
在集合
上的最小值点,因此在一定正则条件下,点
为拉格朗日函数
的鞍点,即满足下面的鞍点不等式
(2.8)
鞍点不等式(2.8)可以等价地表示为
(2.9)
如果函数
关于第二元w是可微的,即
存在,根据(2.8)和(2.9)可以得到下面的变分不等式组
(2.10)
根据投影算子的定义及引理2.1,将变分不等式组(2.10)可表示为投影算子方程组
(2.11)
其中
和
为到集合
和正卦限
上的投影,
是参数。
下面对变分不等式组(2.10)进行计算,对(2.10)的第一个不等式展开
(2.12)
如果
是凸的和可微的,运用性质2.2中的(2.3),(2.12)的第二项可以写成
(2.13)
由(2.13)式代入到(2.10)得到新的变分不等式组
(2.14)
注2.1:经过上述讨论,可以得到当
是对称函数,且
关于第二元w是可微的,进一步如果
是凸的和可微的,则(2.8)-(2.14)表达式彼此相互等价。
3. 二阶微分方程方法
在Antipin [1] 工作的基础上,通过投影算子方程组(2.11)建立具有控制过程的二阶微分方程系统如下
(3.1)
其中
(3.2)
为控制过程,可以提高二阶微分方程系统轨迹的收敛速度,其中
且
均是参数。如果
且
,这时系统(4.19)可退化为Antipin [1] 中的具有控制过程的一阶微分方程系统(6.2),因此具有控制过程的二阶微分方程系统(3.1)和(3.2)是对Antipin [1] 中的一阶微分方程系统(6.2)的推广。以下为了书写方便,记
。
假设函数
,F和
都是Lipschitz连续的,其Lipschitz常数分别为
,
和
。若当
时,
有界,即存在
使得
。则根据上述条件及投影算子的非扩张性和微分方程系统(3.1)和(3.2),得到下面的不等式
(3.3)
和
(3.4)
其中
。(3.3)和(3.4)在具有控制过程的二阶微分方程系统(3.1)的轨迹的收敛性定理证明过程中起着重要的作用。
通过投影算子的定义和引理2.1将微分方程系统(3.1)转换成下面的变分不等式组
(3.5)
(3.6)
(3.7)
(3.8)
下面证明具有控制过程的微分方程系统(3.1)的轨迹的聚点就是具有双约束条件的变分不等式(1.1)的解。
定理3.1:假设具有双约束条件的变分不等式(1.1)的解集非空,映射
是单调的和Lipschitz连续的,其Lipschitz常数为
,映射
是对称函数,且关于第二元w对任意v是可微的,且
是凸的,
和
都是Lipschitz连续,其Lipschitz常数分别为
和
。假设当
时,
,及当
时,
,
有界,
是非空闭凸集合。当
和
时,其中
,具有控制过程的二阶微分方程系统(3.1)的轨迹的聚点是具有双约束条件的变分不等式(1.1)的解。
证明:在(3.5)中令
,在(3.7)中令
分别得到
(3.9)
和
(3.10)
对(3.10)式子展开得到
(3.11)
由内积与范数的关系及(3.4),(3.11)计算后可以得到
(3.12)
将(3.9)和(3.12)相加可得
(3.13)
由于映射
是对称函数,且
是凸的,根据性质2.2的(2.3),(3.13)的第四项可以转化为
(3.14)
将(3.14)代入(3.13)后可得
(3.15)
令(2.10)中第一式
然后加到(3.15)中得
(3.16)
在(3.6)中令
,在(3.8)中令
分别得到
(3.17)
和
(3.18)
利用定理中的Lipschitz条件,运用(3.3)对上式中的第二项进行计算得到
将上式和(3.18)相加得到
(3.19)
由于
,则(3.19)式可以得到
(3.20)
将(3.16)和(3.20)相加,又因为
是单调的映射,则有
(3.21)
由下面关系
对(3.21)继续计算得到
(3.22)
根据已知条件
,
,
,因此
,
和
。
在(3.22)中,令
,并对(3.22)各项从
到t进行积分得
(3.23)
其中B为常数如下表示
由于已知当
时,
和
有界,而
因此
是有界的。根据(3.23)可知,存在常数
使得
(3.24)
对(3.24)式又可以写作
即
(3.25)
对(3.25)两边从
到t进行积分得
其中
为常数。进一步整理得
(3.26)
显然,(3.26)表明当
时,
有界。由于函数
,显然轨迹
也是有界的。存在常数
,
(3.27)
下证
,
,
,
,
,和
成立。
首先证明
是有界的。由不等式(3.23)得
(3.28)
其中
为常数。
由于
,而
,又因为
则不等式(3.28)可以化简为,
(3.29)
由于
,在由(3.27)可以得到
是有界的,可以表示如下
(3.30)
由于
是有界的,且
,因此
有界,根据(3.23)存在常数
有
(3.31)
由不等式(3.31)可得:当
时,下式成立
假设存在一个常数
,对所有的
有,
,
,
,
,
和
成立,这和上式的积分收敛矛盾。因此必存t的子序列
,当
时,
,
,
,
,
和
成立。又因为已证得
和
都是有界的,可知
和
也是有界的。取
的子序列
,则必存在
和
,当
时,
,
,且依然有
,
,
,
,
和
成立。
在微分方程系统(3.1)和(3.2)中取
,当
时得到
上式与(2.11)一致,这就说明
是具有双约束条件的变分不等式(1.1)的解。证毕。
4. 数值结果
本节,我们将通过具有控制过程的二阶微分方程系统(3.1)求解两个具有双约束条件的变分不等式,以验证该方法的有效性。应用Matlab R2019a软件进行计算。在求解的过程中, 所采用的具体算法是微分方程求解函数ode45,这个函数采用的是四阶五级的Runge-Kutta方法。计算机的配置为:CPU Intel(R) Core(TM) i7-7700HQ @2.80 GHz;内存为16.0 GB。
例1考虑双约束变分不等式问题
(4.1)
其中
其解为
。
图1描绘了具有双约束变分条件的不等式问题(4.1)的具有控制过程的二阶微分方程系统(4.19)的轨迹随时间的变化关系,其中该图的曲线是微分方程系统(3.1)的轨迹从三个不同的初始点生成。微分方程系统(3.1)的轨迹
收敛于点
,即问题(4.1)的近似解。
例2考虑双约束变分不等式问题
(4.2)
其中,
其解为
。
Figure 1. Trajectories convergence of the second-order differential equation system with the control process (3.1) for solving problem (4.1)
图1. 问题(4.1)的具有控制过程的二阶微分方程系统(3.1)的轨迹的收敛性
图2描绘了具有双约束变分条件的不等式问题(4.2)的具有控制过程的二阶微分方程系统(3.1)的轨迹随时间的变化关系,其中该图的曲线是微分方程系统(3.1)的轨迹从三个不同的初始点生成。微分方程系统(3.1)的轨迹
收敛于点
,即问题(4.2)的近似解。
Figure 2. Trajectories convergence of the second-order differential equation system with the control process (3.1) for solving problem (4.2)
图2. 问题(4.2)的具有控制过程的二阶微分方程系统(3.1)的轨迹的收敛性
5. 结论
本文首先介绍了双约束条件的对称函数的定义和性质,将具有双约束条件的变分不等式看作一类特殊的优化问题,利用其拉格朗日函数和投影算子的定义和性质,得到了双约束变分不等式的等价投影算子方程组。在通过该算子方程组建立了求解具有双约束条件的变分不等式的具有控制过程的二阶微分方程系统,并证明了该二阶微分方程系统的聚点是具有双约束条件的变分不等式的解。二阶微分方程系统的建立后,与Antipin [1] 不同,本文给出了两个算例说明该方法的有效性。
此外,运用本微分方程方法可以用来求解优化问题、不动点问题等也是一个值得研究的方向。
基金项目
国家自然科学基金青年基金(编号:11801381)。