一个求解变分不等式问题的投影算法

２００５年３月第２２卷第１期

重庆师范大学学报（自然科学版）

ＪｏｕｍａｌｏｆＣｈｏｎｇｑｉｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）

Ｍａｒ．２００５

Ｖ０１．２２Ｎｏ．１

一个求解变分不等式问题的投影算法＋

王传伟

（曲阜师范大学运筹与管理学院，山东日照２７６８２６）

摘要：基于Ｄ．Ｈａｎ提出的求解变分不等式问题的推广的近似点算法（ｇｅｎｅｒａｌｉｚｅｄｐｒｏｘｉｍａｌｍｅｔｈｏｄ），提出了一个新

的改进算法，该算法的最大特点是在每一步只需要近似求解一个线性方程组系统。并在适当条件下证明了算法的全局收敛性。

关键词：变分不等式；线性搜索；投影；全局收敛

中图分类号：０２２１．２

文献标识码：Ａ文章编号：１６７２石６９３（２００５）０１—０００６—０５

Ａ

ＰｒｏｊｅｃｔｉｏｎＡｌｇｏｒｉｔｈｍｆｏｒＳｏｌｖｉｎｇＶａｒｉａｔｉｏｎａｌＩｎｅｑｕａｌｉｔｉｅｓ

Ｆ附ⅣＧＣｈｕａｎ—ｗｅｉ

（ＣｏｌｌｅｇｅｏｆＯｐｅｒａｔｉｏｎＲｅｓｅａｒｃｈａｎｄＭａｎａｇｅｍｅｎｔＳｃｉｅｎｃｅ，ＱｕｆｕＮｏｒｍａｌＵｎｊｖｅｆｓ毋，ＲｉｚｈａｏＳｈａｎｄｏｎｇ２７６８２６，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：Ｂａｓｅｄ

ｏｎ

ｔｈｅｇｅｎｅｒａｌｉｚｅｄｐｒｏｘｉｍａｌ

ｔｏ

ａｌｇｏｒｉｔｈｍｄｅｖｅｌｏｐｅｄｂｙＤ．Ｈａｎ，ｗｅｐｒｅｓｅｎｔ

ａ

ａｎ

ｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｆｏｒｓｏｌｖｉｎｇ

ｅａｃｈ

ｖａｒｉａｔｉｏｎａｌｉｎｅｑｕａｌｉｔｉｅｓ，ｗｈｉｃｈｏｎｌｙｎｅｅｄｓ

ｔｉｏｎｓ，ｗｅ

ｓｏｌｖｅ

ｌｉｎｅａｒｓｙｓｔｅｍｏｆｅｑｕａｔｉｏｎｓ

ａｐｐｒｏｘｉｍａｔｅｌｙ

ａｔ

ｓｔｅｐ．Ｕｎｄｅｒｍｉｌｄａｓｓｕｍｐ—

ｓｈｏｗｔｈｅｇｌｏｂａｌｃｏｎｖｅｒｇｅｎｃｅｏｆｔｈｅａｌｇｏｒｉｔｈｍ．

Ｋｅｙｗｏｒｄｓ：ｖａｒｉａｔｉｏｎａｌｉｎｅｑｕａｌｉｔｉｅｓ；ｌｉｎｅａｒｓｅａｒｃｈ；ｐｒｏｊｅｃｔｉｏｎ；ｇｌｏｂａｌｃｏｎｖｅｒｇｅｎｃｅ

设Ｃ是Ｒ“中非空闭凸子集，Ｆ：Ｒ”一Ｒ“是连续映射。考虑变分不等式问题，求戈＋∈Ｃ，使得

（Ｆ（ｚ＋），ｚ一戈＋）／＞０，

Ｖ戈∈Ｃ

形Ｈ曲ｊ。但是，外梯度投影算法及其变形一般在每一步迭代中需要执行多次投影，从而引起计算量的增大。为克服这一缺点，人们提出了二次梯度投影算法一’８。。与上述方法不同，Ｄ．Ｈａｎ将ｐｒｏｘｉｍａｌ方法与投影算法相结合提出一个混合的推广近似点算法

（ｇｅｎｅｒａｌｉｚｅｄｐｒｏｘｉｍａｌａｌｇｏｒｉｔｈｍ）［９３，每一步迭代只需

其中＜ ， ＞表示Ｒ“中向量的内积。该问题简记为ＶＩＰ（Ｆ，Ｃ）。在数学规划、经济金融、交通等领域有重要的应用，是近几十年运筹学研究的一个热

占［１Ｉ．

要执行一次到可行集Ｃ上的投影。在该算法的每一迭代步，先求解如下关于Ｙ∈Ｒ”的ｐｒｏｘｉｍａｌ子问题的近似解Ｙ‘∈ｉｎｔ（Ｃ）：

ｃ。（Ｆ（Ｙ）＋７ｈ（Ｙ）～Ｖｈ（戈‘））＋（Ｙ一戈‘）＝ｒ‘

（１）（２）

在众多求解变分不等式问题的算法中，投影算法是最重要的一种，因其在计算过程中小的计算量及存储而引起人们的兴趣。投影算法的主要迭代步骤为戈“１＝Ｐ。［戈‘一ａＦ（戈‘）］，其中Ｏｔ＞０，Ｐｃ是Ｒ“到ｃ上的投影算子。该算法的收敛性需要较强的假设条件，映射函数Ｆ强单调和Ｌｉｐｓｃｈｉｔｚ连续，且步长满足某一条件‘２Ｊ。这限制了投影算法的应用。后来Ｋｏｒｐｅｌｅｖｉｃｈ创立了外梯度投影算法。３Ｊ，它的收敛性仅需要映射函数Ｌｉｐｓｃｈｉｔｚ连续。当映射函数非Ｌｉｓｐｓｃｈｉｔｚ连续，或Ｌｉｐｓｅｈｉｔｚ常数未知时，人们借助Ａｒｍｉｊｏ步长搜索提出了外梯度投影算法的多种变

收稿日期：２００４—１０—１３

满足

Ｉｌｒ。｜｜≤盯｜｜戈‘一Ｙ‘１１

其中ｈ：Ｒ”一Ｒ是一个Ｂｒｅｇｍａｎ函数一，１０］。下一个迭代点由戈‘＋１＝（１一ｔ）Ｐｃ［戈‘一ＣｋＯｌ☆Ｆ（Ｙ‘）］＋ｔｘ‘计算得到，其中

旷％孝斧

㈩

／在适当条件下，该算法产生的迭代点列｛Ｘ‘｝全局收敛到ＶＩＰ（Ｆ，Ｃ）的一个解。但是该算法在每一

＋

资助项目：国家自然科学基金（ＮＯ．１０１７１０５５）；山东省自然科学基金（ＮＯ．Ｙ２００３Ａ０２）

万方数据　

作者简介：王传伟（１９６８．），男，山东泰安人，硕士研究生，主要从事变分不等式问题方面的研究。