一種求解非線性互補問題的filter內(nèi)點算法

龍君,曾三云

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

一種求解非線性互補問題的filter內(nèi)點算法

龍君1,曾三云2

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

利用Armijio條件和信賴域方法,構(gòu)造新的價值函數(shù).首次將內(nèi)點算法與filter技術(shù)結(jié)合起來,提出一種求解非線性互補問題的新算法,即filter內(nèi)點算法.在主算法中使用Armijio型線搜索求取步長,在修復(fù)算法中使用信賴域方法進行適當(dāng)控制以保證算法的收斂性.文章還討論了算法的全局收斂性.最后用數(shù)值實驗表明了該方法是有效的.

非線性互補問題;filter方法;信賴域方法;Armijio條件;全局收斂性

1 引言

內(nèi)點法[1-2]是一種比較成熟的最優(yōu)化方法,有運用內(nèi)點法求解非線性互補問題[3]的文獻,比如文獻[4-6]分別研究了某種特殊形式的非線性互補問題的內(nèi)點算法.文獻[7]提出了filter方法,有不少學(xué)者嘗試將此方法與非線性互補問題結(jié)合起來處理[8-11].本文擬在文獻[12]的基礎(chǔ)上,利用Armijio條件和信賴域方法,構(gòu)造一個新的價值函數(shù),再結(jié)合filter技術(shù),提出一種求解非線性互補問題的新算法,即filter內(nèi)點算法.

在本文中,考慮的非線性互補問題(NCP)形式如下:

其中x∈Rn,f:Rn→Rn為一給定的函數(shù),T為轉(zhuǎn)置符號.易知NCP等價于非光滑方程組: H(x)=min{x,f(x)}=0.很顯然,其零解正好是非線性互補問題(NCP)的解.

其中,Ix(x)={i:fi(x)>xi},Ie(x)={i:fi(x)=xi},If(x)={i:fi(x)

再令Jf(x)=Ix(x)∪Ie(x),定義一個n×n的矩陣A(x),設(shè)其第i列為:

其中ei是第i個位置為1其他全為0的列向量.若則?d∈Rn,(2)式可變?yōu)?

2 預(yù)備知識

2.1 基本性質(zhì)

命題1[12]令是任意的,則對任意的序列和任意的序列有

定義如下價值函數(shù):

其中

由命題1和(4)式,立即可得:

命題2[12]令?x?∈?是任意的.則對任意的序列和使{[(xk)?1]Tdk}有界的dk,有

在后面的算法中,c是可變的罰參數(shù),而ζ是固定的數(shù).由(4)式,有

則?d∈Rn,Φc的方向?qū)?shù)為:

不等式(5)有兩個重要的性質(zhì),歸納如下:

命題3[12]對固定的c>0,以下命題成立:

2)對任意的c>0,t∈R,?a>0,使得

令

其中

由(3)式,(6)-(8)式,有

考慮以下線性系統(tǒng):

其中M(x)=A(x)A(x)T+X?2是對稱正定矩陣,且是(10)式的唯一解,則有d?=?M(xk)?1wc(xk).

對(10)式先移項,然后兩邊同時左乘(d?)T,并由(7)式及M(x)是對稱正定矩陣,可得

于是,有Zc(x;d?)<0?wc(x)/=0.

由此可得,若wc(x)/=0,則d?是Φc(x)在x處的下降方向.

2.2 filter技術(shù)

對于某種最優(yōu)化方法,希望發(fā)現(xiàn)一個滿意的點,它不僅與目標(biāo)函數(shù)相關(guān),而且與約束條件也有聯(lián)系.因此,先定義與NCP問題(1)的目標(biāo)函數(shù)和約束條件相關(guān)的兩個函數(shù):

其中[f(x)]?=max{0,?f(x)},σ是一個常數(shù).而且,x≥0總是得到滿足.

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

由此概念,可以定義一個filter集合,在本文所給的算法中,它將被用作接收或拒絕一個試探點的準(zhǔn)則.

定義2[8]filter集合是(指)這樣(一個)序列點對(h(xk),p(xk))所組成的集合,使得彼此之間不相互占優(yōu).如果點對(hxk,pxk)不被filter集中的其他點對所占優(yōu),則說它是可以接受的.

filter方法就是將這些“好點”放進filter集,記為F.在第k個點處,如果一個新點能被filter集合接收,則更新

為方便起見,記Dk+1={i|hi≥hk,pi≥pk,(i∈)},其中hi=h(xi),pi=p(xi),則

為得到收斂結(jié)果,給出如下的filter準(zhǔn)則:

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

3 filter內(nèi)點算法

本文結(jié)合Armijio條件、信賴域方法和filter技術(shù),提出求解NCP問題的一個新算法,具體步驟如下:

算法1(filter內(nèi)點算法)

步3若||wk||≤δ,則令轉(zhuǎn)步2;

令mk為最小的非負整數(shù)m,使得

步8若θ(xk)=0,停止.否則令k:=k+1,轉(zhuǎn)步2.

需要注意的是,當(dāng)mk≥1時,因為mk滿足(12)式,所以mk?1一定不滿足(12)式,于是有

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

步2計算

步3計算

4 收斂性分析

如同文獻{[14-}17],對于算法1的收斂性分析基于以下假設(shè):

H1:集合xk∈X非空有界;

H2:函數(shù)F(x)在包含于X的開集上二次連續(xù)可微;

H3:在求解(14)時,有

其中β2>0為一正常數(shù);

引理1每一個新的迭代點都被filter集合F接受.

證明由算法1知,新迭代點在步7產(chǎn)生.故新的迭代點xk+1被filter集合接收.于是引理得證.

下面分析由算法1所產(chǎn)生的序列{xk}的收斂性.

定義3[12]向量x≥0被稱為是S-正則的,如果對變量d∈Rn,以下線性不等式有解

引理2[12]假定罰參數(shù)序列c可以無限次更新,x?是子序列{xk:k∈K}的聚點,則序列{uk:k∈K}有一個聚點u?,并滿足:

其中

引理3[12]令是給定的,對任意的d∈Rn,定義:

令θx:為齊一次的函數(shù)且滿足:

考慮以下條件:

(a)x是一個S-正則向量;

即

則有以下結(jié)論:(a)?(b)?(c)?(d).

定理1假設(shè)x?是序列{xk:k∈K}的一個聚點.

1)若算法1中的罰參數(shù)序列{ck}被有限次更新,則

2)若算法1中的罰參數(shù)序列{ck}可以無限次更新,并且x?是S-正則的,則θ(x?)=0.

證明1)因為{ck}被有限次更新,由算法1的步3和步5知,存在指標(biāo)k0和常數(shù)c>0,使得對任意的k≥k0,有||wk||>δ,ck=c.

現(xiàn)假設(shè)(15)不成立,即存在常數(shù)ε>0和子序列{xk:k∈K},使得

其中K?{k0,k0+1,………}.由(9)式中的Φ′(xk;dk)≤Z(xk;dk)和(11)式中的Zc(xk,dk)≤0,可知{Φc(xk):k∈K}是單調(diào)遞減的,而且,(16)式暗示著{Φc(xk):k∈K}下有界.因此,序列收斂.再由(12)和(13)式,有

由命題3中的(2)和(16)式,有

即{xk:k∈K}有界,且對任意的k∈K,有

由此易知,?k∈K,?T>0,使得

當(dāng)||wk||≥δ時,由(7),(10)和(11)式可得,對任意的k∈K,有

再由(17)和(19)式,有

根據(jù)τk的定義,對任意的k∈K,若否則,由(18)式及的某些分量趨于0的事實易知,因此

再注意到(20)式,它意味著

記λk=||dk||.由(20)式,有不難證明{[(xk)?1]Tdk}有界.因此由命題2,有

這與(21)式相矛盾！于是(15)式成立.

2)現(xiàn)假設(shè)θ(x?)/=0.由引理2知,uk:k∈K→u?,不難得知函數(shù)θx(d)=dTu?滿足引理3.又因為x?是S-正則的,且θ(x?)>0,由引理3中的(d)知,存在向量使得dTu?<0,這與引理2相矛盾！于是有θ(x?)=0.

5 數(shù)值實驗

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

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

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

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

其中,“迭代次數(shù)”欄中,括號中的數(shù)據(jù)表示文獻[12]中的結(jié)果.由此可以看出,當(dāng)初始點的選取離解較遠時,結(jié)果還是比較好的.

例2考慮如下測試函數(shù):f(x)=Mx+q,其中矩陣M和向量q分別具有如下形式:

此問題的解為:x?=(1,0,………,0)T.選取的初始點為x0=(1,1,………,1)T,其數(shù)值結(jié)果由表2給出

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

其中“迭代次數(shù)”欄中,括號中的數(shù)據(jù)表示文獻[12]中的結(jié)果.由此可以看出,當(dāng)維數(shù)比較高時,的結(jié)果還是比較理想的.

6 結(jié)論

文獻[12]給出了求解NCP問題的正內(nèi)點算法,而文獻[9-11]提出了用filter方法來求解NCP問題.本文結(jié)合他們的優(yōu)點,提出了一個新的算法,即filter內(nèi)戰(zhàn)算法.在主算法中使用Armijio型線搜索求取步長,在修復(fù)算法中使用信賴域方法進行適當(dāng)控制以保證算法的收斂性.

[1]龔小玉,張明望.求解P?(K)-陣線性互補問題的高階仿射尺度內(nèi)點算法[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2008, 24(4):699-705.

[2]孫清瀅,常兆光,王清河.一個求解線性不等式約束的非線性規(guī)劃的廣義梯度投影內(nèi)點算法[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),1999,15(1):92-98.

[3]雷飛燕.無窮維Hilbert空間中的偽單調(diào)非線性互補問題[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2010,26(3):417-419.

[4]王浚嶺.基于代數(shù)等價路徑的一致P-函數(shù)非線性互補問題的可行內(nèi)點算法[J].應(yīng)用數(shù)學(xué),2007,20(2):351-356.

[5]朱德通,蔡力.線性不等式約束的廣義非線性互補問題的仿射內(nèi)點信賴域方法[J].數(shù)學(xué)年刊:A輯,2010, 31(1):13-34.

[6]陳華平,張明望.單調(diào)非線性互補問題基于一類核函數(shù)的原始-對偶大步校正內(nèi)點算法[J].中國科學(xué)技術(shù)大學(xué)學(xué)報,2011,41(9):796-803.

[7]Fletcher R,Ley ff er S.Nonlinear programming without a penalty function[J].Mathematical Programming, 2002(91):239-269.

[8]聶普炎.優(yōu)化中的篩選法[D].北京:中國科學(xué)院計算數(shù)學(xué)與科學(xué)工程計算研究所博士學(xué)位論文,2002.

[9]Nie P.A filter method for solving nonlinear complementarity problems[J].Applied Mathematics and Computation,2005,167(1):677-694.

[10]Long J,Zeng S.A projection-filter method for solving nonlinear complementarity problems[J].Applied Mathematics and Computation,2010,216(1):300-307.

[11]Long J,Zeng S.A new Filter-Levenberg-Marquardt method with disturbance for solving nonlinear complementarity problems[J].Applied Mathematics and Computation,2010,216(2):677-688.

[12]Ma C,Liang G,Chen X.A positive interior-point algorithm for nonlinear complementarity problems[J]. Applied Mathematics and Mechanics,2003,24(3):355-362.

[13]Pang J S.Newton′s method for B-di ff erentiable equations[J].Journal of Mathematics in Operational Research,1990,15(2):311-341.

[14]Audet C,Dennis J E.Combining pattern search and algorithms for derivative free optimization[J].SIAM Journal on Optimization.2004(14):980-1010.

[15]Fletcher R,Ley ff er S.A Boundle Filter Method for Nonsmooth Nonlinear Optimization[R].Dundee:Department of Mathematics,Scotland,University of Dundee,1999.

[16]Fletcher R,Leyfer S,Toint P L.On the Global Convergence of an SLP-Filter Algorithm[R].Dundee: Department of Mathematics,University of Dundee,1998.

[17]Powell M J D.Convergence Properties of a Class of Minimization Algorithms[C]//Mangasarian O L,Meyer R R,Robinson S M.Nonlinear Programming.New York:Academic Press,1975.

A filter interior-point algorithm for nonlinear complementarity problem

Long Jun1,Zeng Sanyun2
(1.School of Preparatory Education for Minority Nationalities,Jishou University,Jishou416000,China; 2.College of Mathematics and Statistics,Jishou University,Jishou416000,China)

A new merit function is constructed by using Armijio conditions and the trust region method.Then fi rstly combining the interior-point method with filter technique,we propose a new algorithm to solve nonlinear complementarity problem.In the main arithmetic,step length is produced by Armijio type line search,and in the repair algorithm,trust region method is used to properly control so as to ensure the convergence of the algorithm.We also discuss the global convergence of the algorithm.Finally,the numerical experiments show that the method is e ff ective.

nonlinear complementarity problem,filter method,trust region method,Armijio conditions, global convergence

O224

A

1008-5513(2014)03-0245-10

10.3969/j.issn.1008-5513.2014.03.005

2013-11-28.

湖南省教育廳科學(xué)研究項目(10C1126,10B088).

龍君(1973-),博士生,講師,研究方向：最優(yōu)化理論與方法.

2010 MSC:09C30