侯春莉， 王宣戰(zhàn)

(1. 淄博師范高等專(zhuān)科學(xué)校 數(shù)理科學(xué)系，山東省 淄博市 255130；2. 中國(guó)石油大學(xué)(華東) 理學(xué)院，山東省 青島市 266580)

0 引 言

標(biāo)準(zhǔn)的非線性互補(bǔ)問(wèn)題(Nonlinear Complementarity Problem，簡(jiǎn)稱NCP)就是求一個(gè)向量x*∈Rn使得

x*≥0，F(xiàn)(x*)≥0，〈x*，F(xiàn)(x*)〉=0

其中F是Rn到自身的一個(gè)映射，〈·，·〉表示Rn中的內(nèi)積. 當(dāng)S為Rn的非負(fù)卦限時(shí)，VIP(VariationalInequalityProblems)和NCP是完全等價(jià)的.VIP和NCP是應(yīng)用數(shù)學(xué)中的一個(gè)十分重要的研究領(lǐng)域，在數(shù)學(xué)規(guī)劃、力學(xué)、工程、經(jīng)濟(jì)、交通等許多領(lǐng)域有廣泛的應(yīng)用[1，2].此處將利用非線性互補(bǔ)問(wèn)題的價(jià)值函數(shù)，結(jié)合Gu.N.Z.[3]的非單調(diào)搜索技術(shù)提出新的求解非線性互補(bǔ)問(wèn)題的非單調(diào)下降算法，該算法中的Gu.N.Z.的非單調(diào)技術(shù)繼承了Grippo[4]，ZhangH.C.[5]非單調(diào)技術(shù)優(yōu)點(diǎn),同時(shí)避免了M，ηk，Qk參數(shù)選取，進(jìn)一步增大了搜索步長(zhǎng)，減少了迭代次數(shù)，加快了算法收斂；并在F(x)為強(qiáng)單調(diào)時(shí)，證明了算法的全局收斂性；用數(shù)值例子驗(yàn)證算法的有效性.

1 算 法

Solodov在文獻(xiàn)[6]中提出的價(jià)值函數(shù)引起人們的極大興趣，它將NCP等價(jià)轉(zhuǎn)化為一個(gè)帶有簡(jiǎn)單非負(fù)約束的優(yōu)化問(wèn)題. 文獻(xiàn)[6]的價(jià)值函數(shù)定義如式(1)：

(1)

其中xi和Fi(x)分別表示向量x和F(x)的第i個(gè)分量，ψ：R2→R，

(2)

由文獻(xiàn)[6]可以將非線性互補(bǔ)問(wèn)題(NCP)等價(jià)轉(zhuǎn)化為一個(gè)帶有非負(fù)約束的最優(yōu)化問(wèn)題

minΨ(x)

s.t.x≥0

由式(1)(2)給出價(jià)值函數(shù)Ψ(x)的梯度

定義

(3)

其中X=diag(x1，x2，...，xn).下面由引理1說(shuō)明d是一個(gè)可行方向，進(jìn)一步由引理2說(shuō)明d是一個(gè)下降方向.

引理1 設(shè)xk≥0是算法(NCPNMDA)產(chǎn)生的第k個(gè)迭代點(diǎn)，xk+1是算法(NCPNMDA)產(chǎn)生的第k+1個(gè)迭代點(diǎn)，由算法(NCPNMDA)知，λk為迭代步長(zhǎng)，dk是由式(5)定義的.如果

則有xk+1=xk+λkdk≥0.

證明對(duì)于每一個(gè)分量

下面，假定映射F在Rn上是強(qiáng)單調(diào)的，即?μ>0，使得

〈F(x)-F(y)，x-y〉≥μ‖x-y‖2， ?x，y∈Rn

引理2 假設(shè)F(x)是連續(xù)可微的且是模為μ強(qiáng)單調(diào)的，則dk是價(jià)值函數(shù)Ψ(x)在xk處的一個(gè)下降方向，即▽?duì)?x)Td≤0.

證明由F(x)是模為μ強(qiáng)單調(diào)的，即

〈F(x)-F(y)，x-y〉≥μ‖x-y‖2，?x，y∈Rn

則有

〈▽F(x)y，y〉≥μ‖y‖2

(4)

由xi∈R+和Fi(x)∈R，再由式(2)有

因此

(5)

故由式(4)(5)得

-μ‖d‖2≤0

(6)

下面給出新的非單調(diào)下降算法(NCPNMDA)的具體步驟：

Step1 若Ψ(xk)=0或者Ψ(xk)<ε，則停，即xk是非線性互補(bǔ)問(wèn)題的一個(gè)解，否則轉(zhuǎn)Step2；

Step2 由式(3)知

(7)

轉(zhuǎn)Step3；

Step3 mk是滿足式(8)的最小非負(fù)整數(shù)

Ψ(xk+ωkmkdk)≤Dk+δωkmk〈▽?duì)?xk)，dk〉

(8)

其中ωk=min{ω，tk}，令λk=ωmk，轉(zhuǎn)Step4；

Step4 xk+1=xk+λkdk，轉(zhuǎn)Step5；

Step5 給出滿足某種規(guī)則的ηk∈[ηmin，ηmax]，計(jì)算

Dk+1=ηkDk+(1-ηk)Ψ(xk+1)

(9)

k：=k+1，轉(zhuǎn)Step1.

注：當(dāng)η=0時(shí)，該算法(NCPNMDA)就退化為單調(diào)下降算法，記為NCPMDA.

2 收斂性分析

引理3 {xk}是算法(NCPNMDA)產(chǎn)生的無(wú)窮序列，則有

(i) Ψ(xk+1)≤Dk，?k；

(ii) Ψ(xk)≤Dk，?k.

證明由式(6)(8)知

Ψ(xk+1)≤Dk+δλk〈▽?duì)?xk)，dk〉≤Dk-μ‖dk‖2

(10)

因此，Ψ(xk+1)≤Dk，?k.

由式(9)(10)知

Dk+1=ηkDk+(1-ηk)Ψ(xk+1)≥ηkΨ(xk+1)+(1-ηk)Ψ(xk+1)=Ψ(xk+1)

又由D0=Ψ(x0)知

Ψ(xk)≤Dk，?k

證畢.

引理4 {xk}是由算法(NCPNMDA)產(chǎn)生的無(wú)窮序列，則{Dk}單調(diào)不增且有界.

證明由算法(NCPNMDA)的構(gòu)造和引理3的(i)知

Dk+1=ηkDk+(1-ηk)Ψ(xk+1)≤ηkDk+(1-ηk)Dk=Dk

再由Ψ(xk)≥0和引理3的(ii)知{Dk}單調(diào)不增且有界. 證畢.

定理1[7]假設(shè)F是模為μ強(qiáng)單調(diào)的，則水平

是有界的.

記子列為{xkj}，則‖F(xiàn)(xkj)‖→∞，又由F是連續(xù)的，有

‖xkj‖→∞，kj→∞

(11)

則式(11)與定理1結(jié)論xk有界矛盾，故結(jié)論得證.證畢.

定理2 假設(shè)F(x)是連續(xù)可微的且是模為μ強(qiáng)單調(diào)的，{xk}是由算法(NCPNMDA)產(chǎn)生的無(wú)窮序列，則{xk}的任一聚點(diǎn)是NCP的一個(gè)解.

由算法(NCPNMDA)的構(gòu)造和式(7)(8)得

即Dk+1-Dk≤(1-ηk)(δλk〈▽?duì)?xk)，dk〉).

由引理2知

Dk+1-Dk≤-(1-ηk)μδλk‖dk‖2

由搜索規(guī)則知，對(duì)?k∈N0，有

Ψ(xk+ω-1λkdk)-Ψ(xk)≥Ψ(xk+ω-1λkdk)-Dk>δω-1λk〈▽?duì)?xk)，dk〉

利用中值定理有

〈▽?duì)?ξk)，dk〉>δ〈▽?duì)?xk)，dk〉

(12)

其中，ξk=xk+θkω-1λkdk，θk∈(0，1).

由式(12)得

〈▽?duì)?x*)，d*〉>δ〈▽?duì)?x*)，d*〉

(13)

由式(6)得

〈▽?duì)?x*)，d*〉≤-μ‖d*‖2

(14)

由式(13)(14)得‖d*‖=0，即由文獻(xiàn)[6]引理2.1知，x*是NCP的一個(gè)解.證畢.

由定理2和文獻(xiàn)[8]可以得到推論1.

推論1 假設(shè)F：Rn→Rn是連續(xù)可微且強(qiáng)單調(diào)的，則NCP有唯一解.

3 數(shù)值試驗(yàn)

運(yùn)用MATLAB語(yǔ)言對(duì)本節(jié)算法編寫(xiě)程序，在ThinkPadT430電腦上對(duì)參考文獻(xiàn)[6][8]中的數(shù)值例子進(jìn)行數(shù)值試驗(yàn)，同時(shí)與單調(diào)步長(zhǎng)的算法進(jìn)行比較.

記本章算法為算法NCPNMDA，單調(diào)線搜索下降算法為算法NCPMDA，并將這兩個(gè)算法的數(shù)值結(jié)果進(jìn)行比較.取ω=0.5，δ=0.85，η=0.3，ε<10-5，從任意大于0的初始點(diǎn)開(kāi)始，來(lái)驗(yàn)證算法的有效性.用x表示初始值，用n表示初始點(diǎn)的維數(shù)，用k表示算法的迭代次數(shù).兩個(gè)例子的F都是在Rn上強(qiáng)單調(diào)的，對(duì)應(yīng)的NCP有唯一解.在數(shù)值結(jié)果中，迭代次數(shù)是指主算法的迭代次數(shù).

例1 設(shè)F(x)=Mx+q，其中

表1給出了不同維數(shù)n和不同初始點(diǎn)x的數(shù)值結(jié)果，圖1給出了計(jì)算分析圖.

表1 例1的計(jì)算結(jié)果

圖1 例1的計(jì)算分析圖

例2 設(shè)F(x)=Mx+q，其中

表2給出了不同維數(shù)n和不同初始點(diǎn)x的數(shù)值結(jié)果，圖2給出了計(jì)算分析圖.

表2 例2的計(jì)算結(jié)果

圖2 例2的計(jì)算分析圖

通過(guò)上述數(shù)值例子的計(jì)算結(jié)果可以看出，從低維到高維，再到初始點(diǎn)的取值，新算法(NCPNMDA)都能快速有效地求得最優(yōu)解，并且具有良好的穩(wěn)定性；無(wú)論從迭代次數(shù)還是運(yùn)行時(shí)間都遠(yuǎn)遠(yuǎn)少于單調(diào)算法(NCPMDA).因此，新算法(NCPNMDA)是有效的，適合求解中大規(guī)模問(wèn)題.

參考文獻(xiàn)：

[1] TANG J Y， DONG L. A New Class of Non-monotone Memory Gradient Method and Its Global Convergence[J]. Mathematical Theory and Applications， 2009， 29(2)：5-8

[2] 烏彩英，陳國(guó)慶. 大規(guī)模非線性互補(bǔ)問(wèn)題的共軛梯度法[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2012，42(3)：185-193

[3] GU N Z， MO J T. Incorporating Nonmonotone Strategies Into the Trust Region Method for Unconstrained Optimization[J]. Computers & Mathematics with Applications， 2008， 55(9)：2158-2172

[4] GRIPPO L， LAMPARIELLO F， LUCIDI S. A Nonmonotone Line Search Technique for Newton’s Method [J]. SIAM Journal on Numerical Analysis，1986， 23(4)：707-716

[5] ZHANG H C， HAGER W W. A Non-monotone Line Search Technique and Its Application to Unconstrained Optimization [J]. SIAM Journal on Optimization， 2004， 14(4)：1043-1056

[6] SOLODOV M V. Stationary Points of Bounded Constrained Minimization Reformulations of Complementarity Problems [J]. Journal of Optimization Theory and Applications， 1997， 94(2)：449-467

[7] WANG Y J， WANG C Y. A Descent Algorithm for Solving Nonlinear Complementarity Problem[J]. Or Transactions， 2004(5)：60-66

[8] GEIGER C， KANZOW C. On the Resolution of Monotone Complementarity Problems [J]. Computational Optimization and Applications， 1996， 2(5)：155-173