龍 君, 曾三云

(吉首大學(xué) 1.民族預(yù)科教育學(xué)院； 2.數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，湖南 吉首 416000)

求解非線性互補(bǔ)問題的兩步迭代-Filter方法

龍 君1, 曾三云2

(吉首大學(xué) 1.民族預(yù)科教育學(xué)院； 2.數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，湖南 吉首 416000)

利用牛頓迭代法作為預(yù)測步，用不動點(diǎn)迭代法作為修正步，結(jié)合filter技術(shù)，提出了求解非線性互補(bǔ)問題的兩步迭代-filter算法，并證明了算法的局部三階收斂性，最后通過數(shù)值實(shí)驗(yàn)表明該算法的有效性.

非線性互補(bǔ)問題； filter方法； 牛頓迭代法； 三階收斂

1 引言

在本文中，考慮如下形式的非線性互補(bǔ)問題(NCP)[1-2]:

(1)

其中x∈Rn,f∶Rn→Rn為給定的函數(shù)f(x)=(f1(x),f1(x),…,f1(x))，其性質(zhì)將在后面給出.

許多學(xué)者利用NCP函數(shù)把問題(1)轉(zhuǎn)化成非光滑方程組，再用解方程組的技巧來求解.NCP函數(shù)φ∶R2→R有如下特性：

在本文中，筆者將使用函數(shù)及其近似光滑，即定義φ及φξ∶R2→R分別為

通過使用函數(shù)φξ，非線性互補(bǔ)問題可等價地轉(zhuǎn)化為如下非線性方程組：

(2)

其中F∶Rn→Rn定義為

2 預(yù)備知識

2.1 兩步迭代法

將F(x)在xk處進(jìn)行一階泰勒展開，可得

F(x)=F(xk)+F′(xk)(x-xk)+O(‖x-xk‖2).

去掉誤差項(xiàng)O(‖x-xk‖2)，即為

令x=xk+1，可得簡易牛頓法

(3)

若F(xk+1)=0，則進(jìn)一步得到牛頓迭代法

(4)

若將F(x)在xk+1處進(jìn)行一階泰勒展開，并去掉誤差項(xiàng)，可得

令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)

由于以上迭代法為隱函數(shù)方法，故文獻(xiàn)[3]中使用牛頓法(4)作為預(yù)測步，而將迭代法(6)作為修正步，構(gòu)造了兩步迭代法.本文中我們將引入filter技術(shù)，構(gòu)造新的算法.

2.2Filter技術(shù)

對于某種最優(yōu)化方法，人們總是希望發(fā)現(xiàn)一個滿意的點(diǎn)，它不僅與目標(biāo)函數(shù)相關(guān)，而且與約束條件也有聯(lián)系.因此，先定義如下兩個函數(shù)：

h(x)=‖[f(x)]-‖,p(x)=‖xTf(x)‖2+σh(x),

其中[f(x)]-=max{0,-f(x)},σ是一個常數(shù).

定義1[4]一個點(diǎn)對(h(xk),p(xk))占優(yōu)另一個點(diǎn)對(h(xi),p(xi))當(dāng)且僅當(dāng)h(xk)≤h(xi)且p(xk)≤p(xi)，記作xk≤xi.

定義2[4]Filter集合是由所組成的集合，它們彼此之間不相互占優(yōu).如果點(diǎn)對不被filter集合中的其他點(diǎn)對所占優(yōu)，則說它是可以接受的.

其中hi=h(xi),pi=p(xi)，則

為得到收斂結(jié)果，我們給出如下filter準(zhǔn)則[5]：

其中第一個不等式表示h下降，第二個不等式表示p充分下降，這個準(zhǔn)則可以保證下一節(jié)中的主算法1所產(chǎn)生的迭代點(diǎn)趨向可行解.

3 兩步迭代-Filter算法

利用牛頓迭代法作為預(yù)測步，用不動點(diǎn)迭代法作為修正步，結(jié)合filter技術(shù)，提出了求解非線性互補(bǔ)問題的兩步迭代-filter算法，具體步驟如下：

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

步1.(預(yù)測步)計(jì)算如下預(yù)測算子

(7)

步2.(修正步)計(jì)算如下修正算子

(8)

步4.(終止條件)若‖F(xiàn)(xk+1)‖≤ε1或‖xk+1-xk‖≤ε2，則停止，否則轉(zhuǎn)步1.

下面給出此算法對應(yīng)的修復(fù)算法，步驟如下：

算法2[修復(fù)算法]

步2.計(jì)算

步3.計(jì)算

4 收斂性分析

如同文獻(xiàn)[6-7]，對于算法1的收斂性分析基于以下假設(shè)：

H1：集合{xk}∈X非空有界；

H2：函數(shù)f(x)在包含于X的開集上二次連續(xù)可微；

引理3[8](1)若有無窮個點(diǎn)進(jìn)入filte集合r，則僅有有限個點(diǎn)與修復(fù)算法相關(guān)；

由算法1的步3易知，若有無窮個點(diǎn)進(jìn)入filter集合，則ξk→0(k→∞)，這表明φξk→φ.借鑒文獻(xiàn)[3]，得到如下收斂性定理.

定理1 設(shè)F∶?Rn→Rn是包含非線性方程組(2)的解x*的在凸集D上的充分可微函數(shù)，則算法1產(chǎn)生的迭代點(diǎn)局部三階收斂且滿足如下殘差方程：

證明 為了討論算法的收斂性，即討論xk+1-x*與xk-x*的關(guān)系，我們先給出yk-xk，并將F(x),F′(x)在xk處進(jìn)行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)

下面分別計(jì)算αI+βF′(yk)F′(xk)-1,F(yk)+F(xk)和F(yk)，以便得到xk+1-x*與xk-x*的關(guān)系.

首先計(jì)算F(yk)：

將F(x)在xk處進(jìn)行Taylor展開，得到

(10)

將F′(x)也在xk處進(jìn)行Taylor展開，得到

(11)

對(10)式，令x=x*，得

整理，得

對上式兩邊同時左乘F′(xk)-1，并注意到y(tǒng)k-xk=-F′(xk)-1F(xk)，得

(12)

對(10)式，令x=yk，并利用(12)式，得

其次計(jì)算αI+βF′(yk)F′(xk)-1：

對(11)式，令x=yk，并利用(12)式，得

于是，有

(13)

最后計(jì)算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 數(shù)值實(shí)驗(yàn)

本文給出算法的一些數(shù)值結(jié)果：終止條件為:ε=10-13.

例1 考慮如下測試函數(shù)：

此問題有兩個解：

選取不同初始點(diǎn)的數(shù)值，結(jié)果由表1給出.

表1 問題1的數(shù)值結(jié)果

注：“迭代次數(shù)”欄中括號里的數(shù)據(jù)是文獻(xiàn)[9]中的結(jié)果.

由表1可以看出，當(dāng)初始點(diǎn)的選取離解較近時，收斂速度是比較快的.

例2 考慮如下測試函數(shù)：

f(x)=Mx+q,

其中矩陣M和向量q分別具有如下形式：

此問題的解為：

選取的初始點(diǎn)為x0=(1,1,…,1)T，其數(shù)值結(jié)果由表2給出.

表2 問題2的數(shù)值結(jié)果

注：“迭代次數(shù)”欄中括號里的數(shù)據(jù)是文獻(xiàn)[9]中的結(jié)果.

由表2可以看出，當(dāng)維數(shù)比較高時，收斂速度是比較理想的.

6 結(jié)論

文獻(xiàn)[3]給出了求解非線性方程組的兩步迭代法，而文獻(xiàn)[5,8]研究了用filter方法求解NCP問題.本文結(jié)合這兩種方法的優(yōu)點(diǎn)，利用牛頓迭代法作為預(yù)測步，用不動點(diǎn)迭代法作為修正步，提出了求解非線性互補(bǔ)問題的兩步迭代-filter算法.當(dāng)?shù)c(diǎn)不能被filter接受時，利用修復(fù)算法進(jìn)行修正.同時還給出了該算法的局部三階收斂性，最后通過數(shù)值實(shí)驗(yàn)表明該算法是有效的.

[1]龍君,曾三云.求解非線性互補(bǔ)問題的無導(dǎo)數(shù)filter方法[J].懷化學(xué)院學(xué)報,2009,28(8):5-9.

[2]龍君,曾三云.一種求解NCP問題的信賴域-SQP-filter算法[J].懷化學(xué)院學(xué)報,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

湖南省教育廳科研項(xiàng)目(10C1126).

龍 君，1973年生，男，湖南鳳凰人，講師，博士研究生，研究方向：最優(yōu)化理論與方法的研究； 曾三云，1980年生，女，湖南邵陽人，副教授，博士研究生，研究方向：運(yùn)籌學(xué).

O224

A

1671-9743(2015)5-0015-06