求解非線性互補問題的非單調(diào)算法*

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

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

0 引 言

標準的非線性互補問題(Nonlinear Complementarity Problem，簡稱NCP)就是求一個向量x*∈Rn使得

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

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

1 算 法

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

(1)

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

(2)

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

minΨ(x)

s.t.x≥0

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

定義

(3)

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

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

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

證明對于每一個分量

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

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

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

證明由F(x)是模為μ強單調(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是非線性互補問題的一個解，否則轉(zhuǎn)Step2；

Step2 由式(3)知

(7)

轉(zhuǎn)Step3；

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

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

(8)

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

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

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

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

(9)

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

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

2 收斂性分析

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

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

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

證明由式(6)(8)知

Ψ(xk+1)≤Dk+δλk〈▽Ψ(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)生的無窮序列，則{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]假設F是模為μ強單調(diào)的，則水平

是有界的.

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

‖xkj‖→∞，kj→∞

(11)

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

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

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

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

由引理2知

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

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

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

利用中值定理有

〈▽Ψ(ξk)，dk〉>δ〈▽Ψ(xk)，dk〉

(12)

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

由式(12)得

〈▽Ψ(x*)，d*〉>δ〈▽Ψ(x*)，d*〉

(13)

由式(6)得

〈▽Ψ(x*)，d*〉≤-μ‖d*‖2

(14)

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

由定理2和文獻[8]可以得到推論1.

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

3 數(shù)值試驗

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

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

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

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

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

圖1 例1的計算分析圖

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

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

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

圖2 例2的計算分析圖

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

參考文獻：

[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ī)模非線性互補問題的共軛梯度法[J]. 數(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