龙 君, 曾三云
(吉首大学 1.民族预科教育学院; 2.数学与统计学院,湖南 吉首 416000)
求解非线性互补问题的两步迭代-Filter方法
龙 君1, 曾三云2
(吉首大学 1.民族预科教育学院; 2.数学与统计学院,湖南 吉首 416000)
利用牛顿迭代法作为预测步,用不动点迭代法作为修正步,结合filter技术,提出了求解非线性互补问题的两步迭代-filter算法,并证明了算法的局部三阶收敛性,最后通过数值实验表明该算法的有效性.
非线性互补问题; filter方法; 牛顿迭代法; 三阶收敛
在本文中,考虑如下形式的非线性互补问题(NCP)[1-2]:
(1)
其中x∈Rn,f∶Rn→Rn为给定的函数f(x)=(f1(x),f1(x),…,f1(x)),其性质将在后面给出.
许多学者利用NCP函数把问题(1)转化成非光滑方程组,再用解方程组的技巧来求解.NCP函数φ∶R2→R有如下特性:
在本文中,笔者将使用函数及其近似光滑,即定义φ及φξ∶R2→R分别为
通过使用函数φξ,非线性互补问题可等价地转化为如下非线性方程组:
(2)
其中F∶Rn→Rn定义为
2.1 两步迭代法
将F(x)在xk处进行一阶泰勒展开,可得
F(x)=F(xk)+F′(xk)(x-xk)+O(‖x-xk‖2).
去掉误差项O(‖x-xk‖2),即为
令x=xk+1,可得简易牛顿法
(3)
若F(xk+1)=0,则进一步得到牛顿迭代法
(4)
若将F(x)在xk+1处进行一阶泰勒展开,并去掉误差项,可得
令x=xk可得新的迭代法
(5)
考虑上面两种方法(3)和(5)的凸组合,即对任取的α>0,β>0,且满足α+β=1,使α×(3)+β×(5),有[3]
xk+1=xk-[αF′(xk+1)-1+βF′(xk)-1][F(xk+1)+F(xk)]+2αF′(xk+1)-1F′(xk+1).
(6)
由于以上迭代法为隐函数方法,故文献[3]中使用牛顿法(4)作为预测步,而将迭代法(6)作为修正步,构造了两步迭代法.本文中我们将引入filter技术,构造新的算法.
2.2Filter技术
对于某种最优化方法,人们总是希望发现一个满意的点,它不仅与目标函数相关,而且与约束条件也有联系.因此,先定义如下两个函数:
h(x)=‖[f(x)]-‖,p(x)=‖xTf(x)‖2+σh(x),
其中[f(x)]-=max{0,-f(x)},σ是一个常数.
定义1[4]一个点对(h(xk),p(xk))占优另一个点对(h(xi),p(xi))当且仅当h(xk)≤h(xi)且p(xk)≤p(xi),记作xk≤xi.
定义2[4]Filter集合是由所组成的集合,它们彼此之间不相互占优.如果点对不被filter集合中的其他点对所占优,则说它是可以接受的.
其中hi=h(xi),pi=p(xi),则
为得到收敛结果,我们给出如下filter准则[5]:
其中第一个不等式表示h下降,第二个不等式表示p充分下降,这个准则可以保证下一节中的主算法1所产生的迭代点趋向可行解.
利用牛顿迭代法作为预测步,用不动点迭代法作为修正步,结合filter技术,提出了求解非线性互补问题的两步迭代-filter算法,具体步骤如下:
算法1[两步迭代-Filter算法]
步1.(预测步)计算如下预测算子
(7)
步2.(修正步)计算如下修正算子
(8)
步4.(终止条件)若‖F(xk+1)‖≤ε1或‖xk+1-xk‖≤ε2,则停止,否则转步1.
下面给出此算法对应的修复算法,步骤如下:
算法2[修复算法]
步2.计算
步3.计算
如同文献[6-7],对于算法1的收敛性分析基于以下假设:
H1:集合{xk}∈X非空有界;
H2:函数f(x)在包含于X的开集上二次连续可微;
引理3[8](1)若有无穷个点进入filte集合r,则仅有有限个点与修复算法相关;
由算法1的步3易知,若有无穷个点进入filter集合,则ξk→0(k→∞),这表明φξk→φ.借鉴文献[3],得到如下收敛性定理.
定理1 设F∶⊆Rn→Rn是包含非线性方程组(2)的解x*的在凸集D上的充分可微函数,则算法1产生的迭代点局部三阶收敛且满足如下残差方程:
证明 为了讨论算法的收敛性,即讨论xk+1-x*与xk-x*的关系,我们先给出yk-xk,并将F(x),F′(x)在xk处进行Taylor展开.
由(7)式易知,yk-xk=-F′(xk)-1F(xk)
对(8)式两边同时减去x*,然后左乘F′(yk),得到
F′(yk)(xk+1-x*)=F′(yk)(xk-x*)-[αI+βF′(yk)F′(xk)-1][F(yk)+F(xk)]+2αF(yk).
(9)
下面分别计算αI+βF′(yk)F′(xk)-1,F(yk)+F(xk)和F(yk),以便得到xk+1-x*与xk-x*的关系.
首先计算F(yk):
将F(x)在xk处进行Taylor展开,得到
(10)
将F′(x)也在xk处进行Taylor展开,得到
(11)
对(10)式,令x=x*,得
整理,得
对上式两边同时左乘F′(xk)-1,并注意到yk-xk=-F′(xk)-1F(xk),得
(12)
对(10)式,令x=yk,并利用(12)式,得
其次计算αI+βF′(yk)F′(xk)-1:
对(11)式,令x=yk,并利用(12)式,得
于是,有
(13)
最后计算F(yk)+F(xk):
(14)
将αI+βF′(yk)F′(xk)-1,F(yk)+F(xk)和F(yk)分别代入(9)式,并整理得到
对上式两边同时左乘F′(yk)-1,并注意到
F′(yk)=F′(x*)+O(xk-x*),F(n)(xk)=F(n)(x*)+O(xk-x*),n=1,2,3.
整理即可得到:
于是定理1得证.
本文给出算法的一些数值结果:终止条件为:ε=10-13.
例1 考虑如下测试函数:
此问题有两个解:
选取不同初始点的数值,结果由表1给出.
表1 问题1的数值结果
注:“迭代次数”栏中括号里的数据是文献[9]中的结果.
由表1可以看出,当初始点的选取离解较近时,收敛速度是比较快的.
例2 考虑如下测试函数:
f(x)=Mx+q,
其中矩阵M和向量q分别具有如下形式:
此问题的解为:
选取的初始点为x0=(1,1,…,1)T,其数值结果由表2给出.
表2 问题2的数值结果
注:“迭代次数”栏中括号里的数据是文献[9]中的结果.
由表2可以看出,当维数比较高时,收敛速度是比较理想的.
文献[3]给出了求解非线性方程组的两步迭代法,而文献[5,8]研究了用filter方法求解NCP问题.本文结合这两种方法的优点,利用牛顿迭代法作为预测步,用不动点迭代法作为修正步,提出了求解非线性互补问题的两步迭代-filter算法.当迭代点不能被filter接受时,利用修复算法进行修正.同时还给出了该算法的局部三阶收敛性,最后通过数值实验表明该算法是有效的.
[1]龙君,曾三云.求解非线性互补问题的无导数filter方法[J].怀化学院学报,2009,28(8):5-9.
[2]龙君,曾三云.一种求解NCP问题的信赖域-SQP-filter算法[J].怀化学院学报,2014,33(5):13-16.
[3]Huang,N.,andMa,C.Convergenceanalysisandnumericalstudyofafixed-pointiterativemethodforsolvingsystemsofnonlinearequations[J].TheScientificWorldJournal,forthcoming,2014.
[4]Fletcher,R.,andLeyffer,S.Nonlinearprogrammingwithoutapenaltyfunction[J].MathematicalProgramming,2002,91:239-269.
[5]Nie,P.Afiltermethodforsolvingnonlinearcomplementarityproblems[J].AppliedMathematicsandComputation,2005,167:677-694.
[6]Long,J.,andZeng,S.Aprojection-filtermethodforsolvingnonlinearcomplementarityproblems[J].AppliedMathematicsandComputation,2010,216:300-307.
[7]Long,J.,andZeng,S.Anewfilter-Levenberg-Marquardtmethodwithdisturbanceforsolvingnonlinearcomplementarityproblems[J].AppliedMathematicsandComputation,2010,216:677-688.
[8]Long,J.,Ma,C.,andNie,P.AnewfiltermethodforSolvingnonlinearcomplementarityproblems[J].AppliedMathematicsandComputation,2007,185:705-718.
[9]Ma,C.,Liang,G.,andChen,X.APositiveInterior-PointAlgorithmforNonlinearComplementarityProblems[J].AppliedMathematicsandMechanics,2003,24:355-362.
Two-Step Iterative-Filter Method for Solving NCP
LONG Jun1, ZENG San-yun2
(1.SchoolofPreparatoryEducationforMinorityNationalities;2.CollegeofMathematicsandStatistics,JishouUniversity,Jishou,Hunan416000)
In this paper,using the Newton iterative method as prediction step and the fixed-point iterative method as correction step,we propose a two-step iterative-filter algorithm for solving nonlinear complementary problem by combining with filter technology,and then we discuss the property of three-order convergence.Finally,the numerical experiments show that the method is effective.
nonlinear complementary problem; filter method; Newton iterative method; three-order convergence
2014-11-21
湖南省教育厅科研项目(10C1126).
龙 君,1973年生,男,湖南凤凰人,讲师,博士研究生,研究方向:最优化理论与方法的研究; 曾三云,1980年生,女,湖南邵阳人,副教授,博士研究生,研究方向:运筹学.
O224
A
1671-9743(2015)5-0015-06