一种求解非线性互补问题的外梯度-Filter方法-论文.pdf

《一种求解非线性互补问题的外梯度-Filter方法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第35卷第4期吉首大学学报(自然科学版)VoI

2、35NO．42014年7月JournalofJishouUniversity(NaturalScienceEdition)Ju1．2014文章编号：1007—2985(2014)04—0019—04一种求解非线性互补问题的外梯度一Filter方法龙君，曾三云(1．吉首大学民族预科教育学院，湖南吉首416000；2．吉首大学数学与统计学院，湖南吉首416000)摘要：结合Josephy—Newton方法，建立了一种不合价值函数的求解非线性互补问题的全局策略．该策略基于外梯度步

3、和Filter技术，提出一个外梯度一Filter算法．此算法中的外梯度步可以减少与最优解之间的距离，从而使该算法具有全局收敛性．在适当的务件下，该算法还具有超线性收敛性．关键词：非线性互补问题；Filter技术；Josephy—Newton方法；外梯度步；收敛性中图分类号：0224文献标志码：AD0I：10．3969／j．issn．1007—2985．2014．04．005考虑如下非线性互补问题(NCP(F))[1-23：F()≥0，xF()一0X≥0，其中向量X∈R”，F：R”一为给定的二次连续函数．非线性互补问题还可

4、以等价地描述为如下的变分不等式问题(VIP(F))，即求一个向量X∈R，使得对任意向量Y∈R，F()(Y～X)≥0．变分不等式与互补问题是2个相伴而生的问题．求解非线性互补问题的算法有很多，例如投影法、内点法、非光滑Newton法、光滑Newton法等叫．最近，文献[-43提出了一种求解单调非线性互补问题的Newton型方法，这种算法有以下优点：(1)从任意的初始点起，由算法所产生的迭代点列收敛到NCP(F)的一个解；(2)算法具有全局收敛性和超线性收敛性；(3)不依赖于任何的价值函数．实际上，求解非线性互补问题还有一种

5、简单的方法叫做外梯度法．一方面，它因计算简单、存贮量小等优点而广受众多学者的关注．另一方面，Filter方法也因其良好的数值结果而广受关注．因此，笔者借鉴文献E13的部分思想，对文献[4—5]中算法进行了适当的修正，即将外梯度法与Filter技术相结合，提出一个外梯度一Filter算法，在较弱的条件下证明了这种方法具有全局收敛性和超线性收敛性．1预备知识1．1基本性质对于一个非空闭凸集s和一点X∈R阜，记x到R车上的投影为Ps()一argminllY—l1．当S—R时，Ps()，∈的计算非常简单，即P”()一max{0，

6、X)=Ex]+．对任意的实数a>0，定义关于口的函数()：一[一口F()]+，并记Y()的自然剩余为E(a，X，F(x))一X—Ex～口F()]+，则E(口，x，F())具有如下性质：1引理1t(i)fIE(口，，F(x))Ii关于口≥0是单调非降的；(“)二flE(a，，F(x))『1关于a>0是单凋非增的．*收稿日期：2013—11—04基金项目：湖南省教育厅科学研究项目(10Cl126，10B088)作者简介：龙君(1973一)，男，湖南凤凰人，吉首大学民族预科教育学院讲师，博士生，主要从事基于Filter方法的理

7、论与算法研究．2O吉首大学学报(自然科学版)第35卷记NCP(F)的解集为X，易知x∈X当且仅当—Y。()．若取口一1，则∈X当且仅当E(1，，F())一一[—F()]+一0．对于一个给定的点x，运用Josephy-Newton方法[6_可求解如下线性互补问题LCP(9~I)：()≥0，xT()0x≥0，(1)其中^()l=F()+(G+^j)(一X)，(2)这里的G是个半正定矩阵，>0为T,~Jl化参数．因为G+I是正定的，所以LCP()有唯一解，其对应的自然剩余为0，即E(I，，())一一[～()]+=o．因此，对于

8、给定的^，LCP(cp★)总可以找到满足IE(1，z，9(z))II≤艿的非精确解1．2Filter技术首先介绍Filter方法的一些相关定义和性质[．对于某种最优化方法，希望发现一个满意的点，它不仅与目标函数相关，而且与约束条件也有联系．现定义与目标函数、约束条件相关的2个函数为h()一l}[F()]一ll，P()=IxF()+()，其中[F()]一=max{0，一F(x))，是一个常数，≥0总是得到满足．定义1【]一个点对(()，P())占优另一个点对(^()，P(x’))，当且仅当h()≤h(‘)且P(‘)≤P(x

9、)，记作x．由此概念，可以定义一个Filter集合，在文中所给的算法中，它将被用作接收或拒绝一个试探点的准则．定义2[。Filter集合是指这样一个序列点对(()，P())所组成的集合，使得彼此之间不相互占优．若点对(^()，P())不被Filter集合中的其他点对所占优，则说它是可以接受的．Filter方法就是将“