非線性互補問題光滑化擬牛頓算法的超線性收斂性

牛瀟萌

（赤峰學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院，內(nèi)蒙古 赤峰 024000）

1 算法

考慮P0函數(shù)非線性互補問題：求x∈R"，使得

其中F是連續(xù)可微的P0函數(shù).

使用如下光滑函數(shù)[1]：

設(shè) z=(μ,x)∈Rn+1,

其中

經(jīng)簡單計算易知H(z)的Jacobian矩陣為

其中塄xΦ(z)T:=[μD1(z)+D2(z)]+[D1(z)+μD2(z)]F'(x),

且 D1(z):=diag{a1(z),…,an(z)}，

設(shè) γ∈(0,1).定義函數(shù) ρ:Rn+1→R+為ρ(z)=γmin{1,||H(z)||2}.

算法1[2]（光滑化擬牛頓算法）

步1 若 ||H(zk)||=0，停.否則，設(shè) ρk:=ρ(zk).若 μk>ρkμ0，解方程 H(zk)+Gk△zk=ρk贊得 △zk=(△μk，△xk)，否則，令 △zk=(△μk，△xk):=（0，△xk），并解方程組 Φ(zk)+Bk△xk=0得 △xk，其中 Gk∈R(n+1)×(n+1)定義為塄且 Bk是塄xΦ(zk)T的一個近似.

步2 若 ||H(zk+△zk)||≤α||H(zk)||-σ1||△zk||2，則設(shè) λk:=1，轉(zhuǎn)步4.

步3 設(shè) λk是取自集合{1,δ,δ2,…}使得 λ=δi滿足如下線搜索的最大數(shù)

步4 zk+1=(μk+1,xk+1)=zk+λk△zk

步5 用如下Broyden-like校正公式修正Bk得Bk+1：

其中 sk=λk△xk=xk+1-xk，yk=Φ(μk,xk+1)-Φ(μk,xk)，參數(shù) θk滿足 |θk-1|≤且 Bk+1非奇異.

步6 令k=k+1，轉(zhuǎn)步1.

2 超線性收斂性分析

引理 1[3]設(shè) H:R++×Rn→Rn+1，Φ：R++×Rn→Rn+1和 v:R++×Rn→Rn+1分別由（3），（4）和（6）定義，則

（i）Φ 在 R++×Rn是半光滑的；

（ii）H是局部Lipschitz連續(xù)的且在R++×Rn是半光滑的.進一步，F(xiàn)'(x)在Rn上是Lipschitz連續(xù)的，則H在R++×Rn是強半光滑的.

為證明超線性收斂性需要如下假設(shè)條件：

假設(shè)條件B

（i）由算法1產(chǎn)生的序列{zk}收斂到H(z)=0的解z*=(μ*,x*)=(0,x*)，其中 H(z)由（3）定義，且 x*是非線性互補問題（1）的嚴格互補解；

(ii)塄xΦ(z*)非奇異.

引理 2[3]假設(shè) H:Rn+1→Rn+1和 Φ:Rn+1→Rn分別由（3）和（4）定義.則

（?。│?在任一點 z=(μ,x)∈Rn+1，μ≠0是連續(xù)可微的.

（ⅱ）H在任一點 z=(μ,x)∈R++×Rn是連續(xù)可微的，其Jacobian矩陣由（5）定義.如果 F是一 P0函數(shù)，則塄xΦ(z)在R++×Rn是非奇異的，從而H'(z)在R++×Rn是非奇異的.

定理1 假設(shè)條件A，B成立，{zk=(μk,xk)}由算法1產(chǎn)生.則存在一常數(shù) ζ>0和一指標k軈，使得當 ζk≤ζ且 k≥時，有λk=1，其中.此外，對于滿足 ζk≤ζ的 k≥，不等式成立.

證明由算法1的步2可知，僅需證明存在一正常數(shù)ζ，使得ζk≤ζ且k充分大時式（7）成立.設(shè)xk+tsk)Tdt.因為μk>0，所以由引理 2（ii）可知 Ak+1非奇異.由假設(shè)條件 B（i）可知 Ak+1趨于塄xΦ(z*)，因為塄xΦ(z*)和 Ak+1非奇異，所以存在一常數(shù)M2>0，使得對充分大的kM2，其余的證明由[4]引理4.4類似可證.

定理2 設(shè)假設(shè)條件A，B成立，{zk}由算法1產(chǎn)生，{zk}是超線性收斂的.

證明由[4]定理4.1類似可證.

3 數(shù)值實驗結(jié)果

本節(jié)提供數(shù)值實驗結(jié)果.結(jié)束準則為

||H(zk)||≤ε=10-6

相關(guān)參數(shù)取 ε=10-6，α=0.9，δ=0.9，σ1=0.8，μ0=10-3，γ=0.2，η=0.5.

算例 1[5]（HS35）這是Hock-Schittkowski收集的第35個問題.這個問題定義為

minf(x)=2x12+2x22+x32+2x1x2+2x1x3-8x1-6x2-4x3+9

s.t.3-x1-x2-x3≥0

xi≥0，i=1，2，3.

這是一個凸規(guī)劃問題，它的Karush-Kuhn-Tucker最優(yōu)性條件導(dǎo)出一個4維單調(diào)互補問題CP（F），其中F(x)定義如下：

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

算例2[6]考慮如下4維非線性互補問題NCP（F），其中F(x)定義如下：

此問題有唯一退化解x*=(2,0,1,0)，計算結(jié)果見表2.

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

算例3[7]這是一組n維線性互補問題，設(shè)F(x)=Mx+q，n階方陣M和n維向量q定義如下:

M是P0矩陣，取初始點x0=(0,…,0)T，計算結(jié)果見表3.

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

〔1〕Huang Z,Han J,Xu D,Zhang L.The non-interior continuation methods for solving the -functin nonlinear complementarity problem[J].Science in China,2011,44:1107-1114.

〔2〕牛瀟萌.非線性互補問題的光滑化擬牛頓算法[J].計算機工程與應(yīng)用,2013(18):33-35.

〔3〕Zhang L P,Han J Y,Huang Z H,Superlinear/Quadratic one-step smoothing New ton method for -NCP[J].Acta Mathematica Sinica,2005(21):117-128.

〔4〕Ma C F,Chen L J,Wang D S.A globally and superlinearly convergent smoothing Broyden-like method for solving nonlinear complementarity problem[J].Applied Mathematics and computation.2008(198):592-604.

〔5〕Hock W,Schittkowski K,Test examples for nonlinear complementariy problems [J].Computati-onal Optim izationand Applications,1996(5):155-173.

〔6〕Yamashita N,Fukushima M,Modified New ton methods for solving a semismooth reformulati-on of monotone complementarity problems[J].Mathematical Programm ing,1997(76):469-491.

〔7〕Chen X J,Ye Y Y,On smoothing methods for the P0-matrix linear complementarity problem[J],SIAM J.Optim.,1997(7):403-420.