牛潇萌

（赤峰学院 数学与统计学院，内蒙古 赤峰 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.定义序列……