求解变分不等式组的新的自适应投影算法

1.1 背景介绍
变分不等式是非线性方程和非线性互补问题等一系列问题的推广, 它在最优化、网络经济、自动控制、信号与图像处理、滤波设计、经济科学、游戏理论,工程力学, 系统识别和数学规划等领域有广泛的应用[15-18]. 在应用数学中, 变分不等式问题是一个相当重要的研究课题, 它不仅在非线性最优化方面具有相当广泛的应用, 而且在力学、控制论、微分方程、工程学、经济均衡理论、对策论、社会和经济模型等方面都有着很好的应用价值. 尤其是物理、数学和工程领域的很多问题都可以转化为变分不等式问题来解决. 它的提出使优化问题和均衡问题的研究得到了统一, 并且在数学领域中作为大量数学问题实际求解的统一模型. 变分不等式的广泛应用, 对工程优化, 经济学和交通运输的均衡问题以及数学各个领域, 计算机科学等方面都作出了重大贡献. 因变分不等式问题和各个领域的紧密联系, 使得大量的数学工作者和经济学家对变分不等式问题的许多理论、方法、思想和技巧作孜孜不倦的研究. 近年来, 关于变分不等式 (VIP) 的研究, 在算法和理论两个方面都有很多的成果, 其中算法多是借助于计算机的MATLAB软件, 使用各种技术和数值计算思想建立各种类型的具体的求解方法; 而理论方面研究的则是对变分不等式的变形和推广 , 例如将变分不等式推广和改进为变分不等式组、拟变分不等式、单值、集值变分不等式、似变分不等式、隐变分不等式、拟 – 似变分不等式、向量变分不等式、随机变分不等式和其他各种类型的广义(或广义混合)变分不等式 .
投影算法是解决变分不等式问题的一种重要工具. 经典的变分不等式问题, 由Stampacchia 在1964年给出并进行了研究; 同年Goldstein[5] 也对变分不等式问题开始进行研究; 1966年Levitin-Polyak[10]对变分不等式问题进行进一步的研究; 1966年Armijo[1]对求解非线性规划问题产生的步长准则作了研究; 1970年Martinet[11]提出邻近点算法; 1976年Rockafellar[14]给出了非精确邻近点算法; 1976年Korpelevich[8]在映射是广义单调的情况下提出外梯度投影算法; 1976年Bertsekas[2]对求解非线性规划问题产生的步长准则再次作了深入探究; 1987年Khobotov[9]提出了一个有用的策略, 设计了一个合适的步长, 对Korpelevich[8]外梯度投影算法作了进一步的完善; 1991年Güller[6]给出了Rockafellar算法中部分步骤在无限维Hilbert空间中非强收敛的一个例子; 1993年Dupuis 和 Nagurney[3]对Goldstein[5]和Levitin-Polyak[10]的投影算法进行改进, 使用了一个预先决定的步长序列; 1996年Nagurney和Zhang提出Nagurney-Zhang[13]投影算法; 1998年Eckstein[4]指出精确求解邻近点算法中的迭代点十分困难, 对此作了进一步的研究和改进; 2002年He[7]改进Goldstein-Levitin-Polyak投影算法求解强单调变分不等式; 在文献[26]中, 王等提出了一种求解变分不等式的外梯度算法,并在此基础上给出了变分不等式解的存在性判定方法.
近年来, 变分不等式理论已经成为研究线性和非线性问题的有力工具. 一般变分不等式[21]是经典变分不等式的一种重要推广, 在科学领域中应用广泛[22, 23], 受到人们越来越多的关注. 而变分不等式组问题是经典变分不等式问题的推广, 2001年, Vema[27]引入并讨论了非线性变分不等式组问题, 在算子T是强单调及Lipschitzian连续的条件下, 给出了一个基于投影技巧的隐式迭代算法. 广义集值混合变分不等式也是经典的变分不等式的一个重要推广, 2003年在文献[25]中首次引入并讨论了它. 在变分不等式问题的研究中, 最重要也是最困难的是提出一种可行并且有效的迭代算法. 对变分不等式的研究很多的学者利用许多方法和不同的技巧（如分解方法、辅助原理、Wiener-Hopf 方程、投影类方法等）提出解一般变分不等式的许多算法[21, 23,  24], 例如: 2002年, Noor[23]构造了另外一种搜索方向并提出了新的投影算法. 在此以后, 用投影算法求解变分不等式问题的研究更加的深入和广泛.
从60年代始, 许多数值计算方法被用于求解变分不等式和相关的优化问题, 如邻近点算法、交替方向法、牛顿型方法、投影算法、内点法等. 因此如何构造算法来求解变分不等式问题是值得研究的. 而投影算法是解的一种简单的算法,[19]介绍了这种算法的一些进展.当投影算法容易计算时, 投影算法是解变分不等式问题相对简单的算法之一. 由于投影算法易于执行、稳健, 可以处理大规模问题, 在求解变分不等式的近似解中起了极大的作用, 因此得到快速发展. 但诸多的投影算法都在一定程度上存在着局限性: 如算法的收敛性需要估计映射的Lipschitz常数和强单调模; 算法的收敛性条件太强; 算法的搜索方向或迭代步长在解附近趋于零的缺点; 收敛速度过慢等因素限制了算法的实用范围. 基于以上考虑, 有必要在已有投影算法的基础上, 分析它们的优点和局限, 克服已有算法的诸多局限,改进已有的投影算法. 因此设计一种可行而宽松的步长准则, 克服了存在的一些局限, 作进一步的研究是必要的.
1.2 变分不等式算法的国内外研究动向
这种投影算法是全局收敛的. 它的有效性严重依赖于Lipschitz常数L的估计和一致强单调模的值. 事实上, 即使是仿射映射, 估计和的值也是困难的.Dupuis 和 Nagurney[3]对Goldstein和Levitin-Polyak的投影算法进行改进, 使用一个预先决定的步长序列满足如下条件:   . 当强单调时, 这种算法依然收敛, 但不足之处是亚线性收敛.
这种算法能够求解单调变分不等式且已经由Marcotte[12]应用到交通分配问题中, 显然, 这种步长对算法的有效性产生了极大的影响. 但是, 假如步长几乎等于0时, 计算机可能直接记为0, 为了避免这种情况, 有必要在步骤3中扩大步长来代替使用一个非增长步长序列. 对Khobotov算法, He[7]对步骤3作出了如下的改进:
1.3本文主要内容概述
本文是如下组织的: 第一章, 介绍变分不等式的背景及求解变分不等式的算法的国内外研究动向; 第二章, 我们首先提出要求解的问题, 其次介绍一些学者已经研究过的与求解变分不等式组相关的性质和引理, 以及在后面章节中需要用到的命题或推论; 第三章, 我们提出了求解变分不等式组的两种算法; 第四章, 我们证明了所提出的两种算法的收敛性; 第五章, 我们讨论了所提出的两种算法的可行性, 并给出了算法2的简单例子以及数值结果; 第六章, 对本文作出总结和展望.

第2章  预备知识
变分不等式问题包括非线性互补问题（当）和非线性方程组（当）, 因此在许多领域都有重要的应用, 包括经济, 运筹学和非线性分析等. 许多作者对这个问题进行了研究[2, 3, 7, 9].
第3章  变分不等式组的新的自适应投影算法
第4章  收敛性分析
4.1对算法1的收敛性分析
4.2  对算法2的收敛性分析
第5章  讨论与数值结果
在本章中, 我们首先讨论本文所提的两个算法的可行性并给出算法2的数值结果. 算法1和算法2都是对文献[7]所提出的算法进行推广, 求解变分不等式组. 但是由于参数选择不同, 投影迭代方程不同. 算法1中投影方程组是隐式的, 不但举例困难, 而且得出数值结果更为不易. 虽然此种改进依然证明了它具有全局收敛性, 但在实际操作中, 不具有可行性. 尽管算法2比算法1具有很好的可行性, 但值得指出的是, 此算法对更一般的变分不等式组同样不适用, 比如严格单调或单调变分不等式组.
接下来, 我们用本文提出的算法2来计算一个简单的例子. 下面我们给出构造的例子:
在算法2中, 由引理4.2.2的证明过程可知, 的值随和的取值不同而变化. 因此我们在实际计算中, 的取值是变化的, 经实验验证, 不管和的取值是多少, 的值在的范围内太接近1或2时, 收敛效果都不理想. 当, 分别取0.1, 0.25, 0.33, 0.5时, 随着的值增大, 迭代次数不断减小, 但是计算的结果随着的值增大, 离精确解更远. 经过多次试验, 发现此算法中, 和的取值非常关键, 当和的取值大于0.75后, 收敛效果很好, 初值均收敛到精确解, 但迭代次数随着的值增大到接近2时相对较多. 当和的取值越小时, 迭代次数也越少, 但不会收敛到精确解.

第6章  结论与展望
6.1 全文总结
本文主要在He B.S., Yang H., Meng Q., 和Han D.R.的文章基础上, 改进算法的参数和投影关系, 提出2种新的算法, 将其算法推广到求解变分不等式组上, 并采用新的自适应投影算法, 在空间中借助的强单调性和Lipschitz连续性, 以及投影的相关性质和引理证明了新的自适应投影算法产生的序列收敛到变分不等式组的唯一解, 然后讨论了2种算法的差异, 并对其中之一构造出了简单的例子, 给出了数值结果和图像.
6.2 研究展望
由于水平有限, 对变分不等式组的研究没有深入和完善, 在今后的学习过程中, 进行进一步研究的还有以下问问题:
在空间中, 进一步改进自适应投影算法,使得变分不等式组收敛速度更快, 并构造出更高维的例子, 给出数值实验验证.
将自适应投影算法求解变分不等式组问题应用到现实生活模型中.