求解非线性互补问题的两步迭代-Filter方法

龙 君, 曾三云

(吉首大学 1.民族预科教育学院； 2.数学与统计学院，湖南 吉首 416000)

求解非线性互补问题的两步迭代-Filter方法

龙 君1, 曾三云2

(吉首大学 1.民族预科教育学院； 2.数学与统计学院，湖南 吉首 416000)

利用牛顿迭代法作为预测步，用不动点迭代法作为修正步，结合filter技术，提出了求解非线性互补问题的两步迭代-filter算法，并证明了算法的局部三阶收敛性，最后通过数值实验表明该算法的有效性.

非线性互补问题； filter方法； 牛顿迭代法； 三阶收敛

1 引言

在本文中，考虑如下形式的非线性互补问题(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 预备知识

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所产生的迭代点趋向可行解.

3 两步迭代-Filter算法

利用牛顿迭代法作为预测步，用不动点迭代法作为修正步，结合filter技术，提出了求解非线性互补问题的两步迭代-filter算法，具体步骤如下：

算法1[两步迭代-Filter算法]

步1.(预测步)计算如下预测算子

(7)

步2.(修正步)计算如下修正算子

(8)

步4.(终止条件)若‖F(xk+1)‖≤ε1或‖xk+1-xk‖≤ε2，则停止，否则转步1.

下面给出此算法对应的修复算法，步骤如下：

算法2[修复算法]

步2.计算

步3.计算

4 收敛性分析

如同文献[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得证.

5 数值实验

本文给出算法的一些数值结果：终止条件为:ε=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可以看出，当维数比较高时，收敛速度是比较理想的.

6 结论

文献[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