擬牛頓算法收斂性證明中的幾個定理

牛瀟萌

（赤峰學院 數學與統計學院，內蒙古 赤峰 024000）

擬牛頓算法收斂性證明中的幾個定理

牛瀟萌

（赤峰學院 數學與統計學院，內蒙古 赤峰 024000）

互補問題是一類重要的優化問題，它在工程、經濟和交通平衡等領域都有重要應用．本文給出了非線性互補問題的光滑化擬牛頓算法，并給出證明此算法全局收斂性的幾個重要定理.

非線性互補問題；擬牛頓；光滑函數

1 非線性互補問題光滑化擬牛頓算法

考慮P0函數非線性互補問題：求x∈R0，使得

其中F是連續可微的P0函數.

使用如下光滑函數[1]：

其中?(μ,a,b)∈R3.

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

其中

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

其中

且

易知對所有i=1,2,…,n有

設γ∈(0,1).定義函數ρ:Rn+1→R+為

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

選一個初始非奇異矩陣B0∈Rn×n.設k=0.

步1若||H(zk)||=0，停.否則，設ρk:=ρ(zk).若μk>ρkμ0，解下面的方程得

否則，令Δzk=(Δμk,Δxk):=(0,Δxk)，并解如下方程組得Δxk，

其中Gk∈R(n+1)×(n+1)定義為

且Bk是▽xΦ(zk)T的一個近似.

步2 若

則設λk:=1，轉步4.

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

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

步6令k=k+1，轉步1.

定理1[2]算法是有定義的，且產生一無窮序列{zk=(μk, xk)}滿足{(μk)}?R++是單調非增的.

2 非線性互補問題光滑化擬牛頓算法收斂性證明中的幾個重要定理的證明

設

定理2[3]設μ>0且?:R++×R2由 (18)定義.設{ak},{bk}是滿足下列條件的兩個序列ak,bk→+∞或ak→-∞或bk→-∞．則對任意(μ,a,b)∈R++×R2,有

定理3假設F是連續可微的P0函數，H(z)由（3）定義，}由算法1產生.令>0，如果對所有的k≥0有μk≥且那么

證明 由定理1知{μk}單調非增，從而對任意k≥0，有.用反證法證明，假設存在一無界序列{xk}，使得||H(μk,xk)||有界.因為序列{xk}是無界的，所以指標集I:={i∈N: {xik}是無界的}是非空的．不失一般性，可假設{|xjk|}→+∞，?j∈I.定義序列}為

其中j是取得max的指標之一，不失一般性，假設j與k是相互獨立的.因為j∈I,所以

現考慮下面兩種情況:

因此由(2)，(4)和定理2可得

因此由(2)，(4)和定理2可得

證明 由（16），（17）可知對所有k，||H(zk+1)||≤(1+ηk)||H (zk)||，從而

所以xk+1∈Lμk+1.

定理5設{zk}由算法1產生，則

證明 由（16），（17）可知對所有k有

其中σ0=max{σ1,σ2}，所以

整個喪禮，桃花像個木頭人，人家叫她怎么做，她就怎么做；只有一件事她做不了，那就是哭喪。自始至終，桃花都沒有哭過。人們對她說話，她充耳不聞，她也不說話，就連兒子黃方永哭著喊著叫她媽媽，她也不理不睬的。事后，人們擔心的事還是發生了；桃花常常忘了回家，確切地說，是找不到家，一個人在田野上瞎走，嘴上喃喃自語：“回去吧！回去……”大家都說桃花丟了魂。黃石、黃羊和黃鹿不得不去把她找回來。而桃花突然清醒過來，是有一天她在田里勞動時，被體內的腳踢了一下；她愣住了，直起身來，輕輕地撫摸肚子；忽然又一腳，她蒼白的臉才一點點地活動起來，就有了活物的神色。

令j→∞且由（12）可得，

引理1[4]設{ak},{tk}是滿足如下條件的正數列ak+1≤，則}收斂.

定理6設{zk}由算法1產生，則序列{||H(zk)||}收斂.

引理2[5]如果F:D?Rn→Rn在凸集D0?D上是可微的且對所有x∈D0，||F'(x)||≤M<+∞，那么F在D0上是Lipschitz連續的.

引理3[6]假設F是連續可微的P0函數且Φ(μ,x)由(4)定義.對任意μ>0和c>0，定義水平集Lμ(c):={x∈Rn:||Φ(μ,x) ||≤c}，則對任意μ2≥μ1>0，集合是有界的.特別地，對任意μ>0和c>0，集合Lμ(c)是有界的.

定理7假設F是連續可微的P0函數且F'(x)在集合L)是Lipschitz連續的，其中Lμ(c):={x∈Rn:||Φ(μ,由（6）定義，則存在使得

證明 由（6）可知

由（11）知

由L(c)定義和引理3知μ,μ'∈[μ1,μ2],x,x'有界.又因為F'連續，所以F'(x')有界.故證明（24）成立，只需證明存在正常數L1,L2,L3,L4，使得

下面只證明（25），（26）類似可證.為證（25）只需證明存在0，使得

為證明簡便引入如下記號：是有界的，不妨設其界分別為M1,M2,M3，則

同理

由L(c)的有界性和F'的連續性知F'在L(c)上是有界的，所以由（28）—（30）以及引理2知（27）成立.

由L(c)的有界性和F的連續性知F在L(c)上有界，從而

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

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

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

〔4〕D.H.Li,M.Fukushima,A derivative-free line search and global connvergence of Broyden-like method for nonlinear equations[J].Optim ization Methods and Software,2000,13:181-201.

〔5〕J.M.O rtega,W.C.Rheinboldt,Iterative solution of nonlinear Equations in several Variables[M].New York, Academic press,1970.

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

0224

A

1673-260X（2014）03-0001-03