单调变分不等式的改进次梯度外梯度算法

张双德， 夏福全， 黄 瑕

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

设H是Hilbert空间，其内积和范数分别表示为〈·，·〉和‖·‖.变分不等式（VI）问题是求x*∈C，使得对∀x∈C，都有

其中C是H中的一个非空闭凸子集，f：C→H是一个映射.变分不等式问题和它的解集分别用VI（C，f）和SOL（C，f）表示.变分不等式问题是优化理论中的一个基本问题，同时在结构分析、工程科学、经济科学、运筹学、自动控制等领域也具有广泛的应用［1-5］.

为了解决变分不等式问题，Korpelevich［1］提出Rn空间中的外梯度算法（EG）：

其中λ＞0，PC是H→C的投影.在f是单调和Lipschitz连续且Lipschitz系数为的条件下，证明了算法所生成的序列收敛到解集中的一点.

在上述外梯度算法（EG）的每次迭代过程中，需要计算两次向C的投影，其中C是一个一般的非空闭凸集，这样的投影不容易实现.为了克服这个困难，Censor等［2］提出一种次梯度外梯度算法，该算法将（1）式中的投影换成向一个特殊结构的半空间Tk的投影：

在映射f是单调和Lipschitz连续且Lipschitz系数为的条件下，证明了上述算法在Hilbert空间中的弱收敛性.接着，为了得到强收敛性，Censor等［6］又提出一种新的次梯度外梯度算法：

其中Tk与（2）式中相同.在f是单调和Lipschitz连续且Lipschitz系数为的条件下，证明了算法在Hilbert空间的强收敛性，但这个算法仍然需要计算一次向闭凸集C的投影，同时对映射f的Lipschitz系数的大小也有要求.

最近，He等［7］提出一种修正次梯度外梯度算法：

其中Tk与（2）式中相同.这个算法的两次投影均是向特殊结构的半空间投影，同时要求其中的βk满足恰当的线性搜索条件，从而不需要知……