牛瀟萌

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

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

牛瀟萌

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

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

非線性互補問題；擬牛頓；光滑函數(shù)

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

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

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

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

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

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

其中

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

其中

且

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

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

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

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

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

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

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

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

步2 若

則設(shè)λk:=1，轉(zhuǎn)步4.

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

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

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

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

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

設(shè)

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

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

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

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

現(xiàn)考慮下面兩種情況:

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

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

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

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

定理5設(shè){zk}由算法1產(chǎn)生，則

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

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

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

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

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

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

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

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

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

證明 由（6）可知

由（11）知

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

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

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

同理

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

由L(c)的有界性和F的連續(xù)性知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].計算機工程與應(yīng)用，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