一種求解非線性互補(bǔ)問(wèn)題的外梯度-Filter方法*1

龍 君,曾三云

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

一種求解非線性互補(bǔ)問(wèn)題的外梯度-Filter方法*1

龍 君1,曾三云2

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

結(jié)合 Josephy Newton方法，建立了一種不含價(jià)值函數(shù)的求解非線性互補(bǔ)問(wèn)題的全局策略.該策略基于外梯度步和Filter技術(shù)，提出一個(gè)外梯度-Filter算法.此算法中的外梯度步可以減少與最優(yōu)解之間的距離，從而使該算法具有全局收斂性.在適當(dāng)?shù)臈l件下，該算法還具有超線性收斂性.

非線性互補(bǔ)問(wèn)題；Filter技術(shù)；Josephy Newton方法；外梯度步；收斂性

考慮如下非線性互補(bǔ)問(wèn)題(NCP(F))[1-2]:

F(x)≥0,xTF(x)=0x≥0,

其中向量x∈Rn,F:Rn→Rn為給定的二次連續(xù)函數(shù).

變分不等式與互補(bǔ)問(wèn)題是2個(gè)相伴而生的問(wèn)題.求解非線性互補(bǔ)問(wèn)題的算法有很多，例如投影法、內(nèi)點(diǎn)法、非光滑Newton法、光滑Newton法等[3].最近，文獻(xiàn)[4]提出了一種求解單調(diào)非線性互補(bǔ)問(wèn)題的Newton型方法，這種算法有以下優(yōu)點(diǎn):(1)從任意的初始點(diǎn)起，由算法所產(chǎn)生的迭代點(diǎn)列收斂到NCP(F)的一個(gè)解;(2)算法具有全局收斂性和超線性收斂性;(3)不依賴于任何的價(jià)值函數(shù).

實(shí)際上，求解非線性互補(bǔ)問(wèn)題還有一種簡(jiǎn)單的方法叫做外梯度法.一方面，它因計(jì)算簡(jiǎn)單、存貯量小等優(yōu)點(diǎn)而廣受眾多學(xué)者的關(guān)注.另一方面，F(xiàn)ilter方法也因其良好的數(shù)值結(jié)果而廣受關(guān)注.因此，筆者借鑒文獻(xiàn)[1]的部分思想，對(duì)文獻(xiàn)[4-5]中算法進(jìn)行了適當(dāng)?shù)男拚?，即將外梯度法與Filter技術(shù)相結(jié)合，提出一個(gè)外梯度-Filter算法，在較弱的條件下證明了這種方法具有全局收斂性和超線性收斂性.

1 預(yù)備知識(shí)

1.1基本性質(zhì)

對(duì)任意的實(shí)數(shù)α>0，定義關(guān)于α的函數(shù)yα(x)∶=[x-αF(x)]+，并記yα(x)的自然剩余為E(α,x,F(x))=x-[x-αF(x)]+，則E(α,x,F(x))具有如下性質(zhì)：

記NCP(F)的解集為X*，易知x∈X*當(dāng)且僅當(dāng)x=yα(x).若取α=1，則x∈X*當(dāng)且僅當(dāng)E(1,x,F(x))=x-[x-F(x)]+=0.

對(duì)于一個(gè)給定的點(diǎn)xk，運(yùn)用Josephy Newton方法[6-7]可求解如下線性互補(bǔ)問(wèn)題LCP(φk):

φk(x)≥0,xTφk(x)=0x≥0,

(1)

其中

φk(x)∶=F(xk)+(Gk+μkI)(x-xk),

(2)

1.2Filter技術(shù)

首先介紹Filter方法的一些相關(guān)定義和性質(zhì)[8].

對(duì)于某種最優(yōu)化方法，希望發(fā)現(xiàn)一個(gè)滿意的點(diǎn)，它不僅與目標(biāo)函數(shù)相關(guān)，而且與約束條件也有聯(lián)系.現(xiàn)定義與目標(biāo)函數(shù)、約束條件相關(guān)的2個(gè)函數(shù)為h(x)=‖[F(x)]-‖,p(x)=‖xTF(x)‖2+σh(x),其中[F(x)]-=max{0,-F(x)},σ是一個(gè)常數(shù)，x≥0總是得到滿足.

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

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

定義2[8]Filter集合是指這樣一個(gè)序列點(diǎn)對(duì)(h(xk),p(xk))所組成的集合，使得彼此之間不相互占優(yōu).若點(diǎn)對(duì)(h(xk),p(xk))不被Filter集合中的其他點(diǎn)對(duì)所占優(yōu)，則說(shuō)它是可以接受的.

2 外梯度-Filter算法

結(jié)合外梯度法與Filter技術(shù)，提出一個(gè)新的算法，即外梯度-Filter算法.

算法1[外梯度-Filter算法]

步驟3(不精確牛頓步) 若‖E(1,xk,F(xk))‖=0，則停.否則，選擇一個(gè)正半定矩陣Gk和μk=‖E(1,xk,F(xk))‖t.取ρk∈[0,1)，計(jì)算由(1),(2)式給出的LCP(φk)的一個(gè)非精確解zk≥0，使得‖E(1,zk,φk(zk))‖≤ρkμk‖xk-zk‖.

步驟4 令yk∶=zk-ek,vk∶=F(yk)-φk(zk)+E(1,zk,φk(zk)),設(shè)εk∶=-vk+μk(xk-yk).若‖εk‖>σkμk‖xk-yk‖，則轉(zhuǎn)步驟6.

下面給出算法1對(duì)應(yīng)的修復(fù)算法.

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

步驟3 計(jì)算

(3)

3 收斂性分析

假設(shè)NCP(F)的解集是非空的.

定義3[9]映射F:Rn→Rn在集合S上是:(ⅰ) 偽單調(diào)的，如果對(duì)任意的向量x,y∈S有F(y)T(x-y)≥0?F(x)T(x-y)≥0；(ⅱ) 單調(diào)的，如果對(duì)任意的向量x,y∈S有[F(x)-F(y)]T(x-y)≥0.

顯然，若F在S上單調(diào)，則它在S上一定偽單調(diào).另外，若映射F是連續(xù)且偽單調(diào)的，則對(duì)應(yīng)的VIP(F)的解集是閉凸集[10].

分析算法的收斂性之前，需要先做一些假設(shè)，具體如下：

(H1) 集合{xk}?X非空有界;

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

(H4) 矩陣序列{Gk}有界;

需要注意的是：(H1)和(H2)是標(biāo)準(zhǔn)假設(shè)；(H3)是個(gè)很弱的充分下降條件(因?yàn)镃auchy步滿足這個(gè)條件)，在文中，它作為一個(gè)充分條件；在信賴域方法里，(H3)能保證全局收斂性；(H4)是得到收斂結(jié)果的重要條件，但它對(duì)局部收斂速度的影響較小.

通過(guò)對(duì)修復(fù)算法的分析，有如下結(jié)論:

引理2[11-12]在假設(shè)(H1)—(H5)條件下，修復(fù)算法有限步終止.

定理1 假設(shè)映射F是連續(xù)和偽單調(diào)的,{xk}由算法1產(chǎn)生,則{xk}是有界的.進(jìn)一步假設(shè)存在常數(shù)C1,C2>0,使得對(duì)于?k,有

則{xk}收斂到NCP(F)的一個(gè)解上.

由于篇幅限制，定理1的證明過(guò)程省略.定理1表明，在較弱的條件下，文中所提出的算法具有全局收斂性.

定理2的結(jié)論滿足了NCP的要求，即F(x)≥0.

借鑒文獻(xiàn)[4]中的證明方法，可以得到文中所給算法的超線性收斂性如下:

定理3[4]假設(shè)映射F是連續(xù)和單調(diào)的，設(shè)x*是NCP(F)的一個(gè)解，在這個(gè)解上，F(xiàn)是可微的且F(x*)正定，設(shè)F在x*的附近是度為p∈(0,1]的局部H?lder連續(xù)的.另外，假設(shè)且從某一指標(biāo)k0起，Gk=F(xk),則序列{xk}Q-超線性收斂到x*.

4 結(jié)語(yǔ)

在迭代過(guò)程中，結(jié)合Josephy Newton方法，對(duì)正交投影步或外梯度步運(yùn)用Filter技術(shù)，提出了一種求解非線性互補(bǔ)問(wèn)題的新算法，并得到此算法的全局收斂性，在適當(dāng)?shù)臈l件下，該算法還具有超線性收斂性.

[1] HORST R,PARDALOS P.Complementarity Problems[M]∥Hankbook of Global Optimization.Boston,Massachusetts：Kluwer Academic Publishers,1995:271-338.

[2] FERRIS M C,PANG J S.Complementarity & Variational Problems:State of the Art[M].Philadelphia VSA:SIAM,1997.

[3] 韓繼業(yè),修乃華,戚厚鐸.非線性互補(bǔ)理論與算法[M].上海:科學(xué)技術(shù)出版社,2006.

[4] SOLODOV M V,SVAITER B F.A Truly Globally Convergent Newton Type Method for the Monotone Nonlinear Complementarity Problem[J].SIAM J. OPTIM,2000,10(2):605-625.

[5] CALAMAIA P H,MORE J J.Projected Gradient Methods for Linearly Constrained Problems[J].Math. Prog.,1987(39):93-11.

[6] BONNANS J F.Local Analysis of Newton Type Methods for Variational Inequalities and Nonlinear Programming[J].Applied Mathematics and Optimization,1994,29(2):161-186.

[7] JOSEPHY N.Newton’s Method for Generalized Equations[R].Madison,Wisconsin:Mathematics Research Center,University of Wisconsin,1979.

[8] FLETCHER R,LEYFFER S.Nonlinear Programming Without a Penalty Function[J].Math. Prog.,2002(91):239-269.

[9] QU Bao,WANG Changyu,ZHANG Shuxi.A Method for Solving Nonlinear Complementarity Problems and Its Convergence Properties[J].Math. Nume. Sini.,2006,28(3):247-258.

[10] FACCHINEI F,PANG JONG SHI.Finite Demensional Variational Inequalities and Complementarity Problems[M].New York：Spring Verlag,2003.

[11] LONG Jun,MA Changfeng,NIE Puyan.A New Filter Method for Solving Nonlinear Complementarity Problems[J].Applied Mathematics and Computation,2007(185):705-718.

[12] LONG Jun,MA Changfeng.A Filter Method for Solving Nonlinear Complementarity Problems Based on Derivative Free Line Search[J].Applied Mathematics and Computation,2007(190):271-286.

[13] LONG Jun,ZENG Sanyun.A Projection Filter Method for Solving Nonlinear Complementarity Problems[J].Applied Mathematics and Computation,2010,216(1):300-307.

[14] LONG Jun,ZENG Sanyun.A New Filter Levenberg Marquardt Method with Disturbance for Solving Nonlinear Complementarity Problems[J].Applied Mathematics and Computation,2010,216(2):677-688.

(責(zé)任編輯 向陽(yáng)潔)

ExtragradientFilterMethodforSolvingNonlinearComplementarityProblems

LONG Jun1,ZENG Sanyun2

(1.School of Preparatory Education for Minority Nationalities，Jishou University,Jishou 416000,Hunan China;2.College of Mathematics and Statistics,Jishou University,Jishou 416000,Hunan China)

Combined with the Josephy Newton method,a new globalization strategy without any merit function was established for nonlinear complementarity problem.The strategy presents an extragradient filter algorithm based on extragradient step and filter technology.The extragradient step can reduce the distance with the optimal solution of the problem.So the resulting algorithm is globally convergent to a solution.Under natural assumptions,locally superlinear rate of convergence can be obtained.

nonlinear complementarity problem;filter technology;Josephy Newton method;extragradient step;convergence

1007-2985(2014)04-0019-04

2013-11-04

湖南省教育廳科學(xué)研究項(xiàng)目(10C1126，10B088)

龍 君(1973- )，男，湖南鳳凰人，吉首大學(xué)民族預(yù)科教育學(xué)院講師，博士生，主要從事基于Filter方法的理論與算法研究.

O224

A

10.3969/j.issn.1007-2985.2014.04.005