解非线性互补问题的非精确正则化算法
丁小妹; 王平
【期刊名称】《《集美大学学报（自然科学版）》》
【年(卷),期】2019(024)006
【总页数】5页(P471-475)
【关键词】非线性互补问题; 全局收敛; 局部超线性收敛; 非精确正则算法
【作 者】丁小妹; 王平
【作者单位】武夷学院数学与计算机学院 福建 武夷山354300
【正文语种】中 文
【中图分类】O224.2
0 引言
考虑非线性互补问题(NCP(F))[1-5]：求向量x∈Rn，使得x≥0,F(x)≥0,xTF(x)=0成立。其中，非线性向量函数F(x):Rn→Rn连续可微。
互补问题作为计算数学与运筹学的一个交叉研究领域，其与变分不等式问题、不动点理论等都有紧密的联系，在力学、工程、经济、交通等许多领域都有广泛的应用，这就使得该领域成为了数学规划中的一个很热门的研究课题。
由于底层函数的导数可能存在严重的病态性，并且可能阻止光滑化方法收敛到问题的解，因此引入正则化技术克服这一缺点，文献[6]首次提出了类似的正则化技术。2010年，唐嘉[2]提出了解P0-函数混合互补问题的一种正则算法，该算法中的正则参数和光滑参数都是彼此独立的变量，并且可以通过线性方程组的迭代很快得到，在不需要严格互补假设的条件下，该算法的全局收敛性和局部超线性收敛性也得到了证明。但是该算法中每一步都要精确求解一个线性方程组，而当方程组的变量较多时，精确求解该方程组的计算量较大。受文献[7-9]的启发，本文建立了求解非线性互补问题的非精确正则化算法。
众所周知，通常将NCP(F)转化为与之等价的方程组问题，即Φ(x)=0。其中，Φ(x):Rn→Rn是半光滑函数，本文中采用Fischer-Burmeister(FB)函数来完成，即那么，则φFB(a,b)=0⟺a≥0,
b≥0,ab=0。但是FB函数在点(0,0)处不可微，通过引入光滑参数μ>0，得到一个光滑FB函数：则φ(0,a,b)=φFB(a,b)。
令z:=(μ,ε,x)∈R++×R++×Rn,
H(z)=(μ ε (Γ(z))T)T,
(1)
Ψ(μ,x):=(φ(μ,x1,F1(x)) … φ(μ,xn,Fn(x)))T,
(2)
Γ(z):=Ψ(μ,x)+εx。
(3)
那么非线性互补问题NCP(F)等价于以下正则化的方程：H(z)=0。经过简单计算，得
(4)
其中，可得，对于任意的i=1,…,n，有0<ai(μ,x)≤e2μ+3μ,0<bi(μ,x)≤e2μ+3μ。
定义1 设C⊂Rn是一非空集合，F:C→Rn是一映射，F=(f1,f2,…，fn)T，如对任意点x,y∈C，x≠y，存在下标k=k(x,y)，1≤k≤n，使得xk≠yk,(xk-yk)(fk(x)-fk(y))≥0，则称F为C中的P0函数。
引理1 设函数H由式(1)定义，函数Γ由式(3)定义，则：ⅰ)对于任意的z:=(μ,ε,x)∈R++×R++×Rn，函数Γ连续可微；ⅱ)对于任意的z:=(μ,ε,x)∈R++×R++×Rn，如果函数F是P0函数，则式(4)定义的函数H′(z)非奇异。
引理2 设F为连续可微的P0函数，H由式(1)定义，则对于任意的μ>0，ε>0，有H关于x强制，即
证明 见参考文献[2]引理1.1.3。
1 非精确正则化算法
本节构造了一种求解非线性互补问题的非精确正则化算法(算法1)。定义价值函数：
(5)
下面给出算法1的具体步骤。
步骤1 选取常数δ∈(0,1)，η,γ,σ,μ0,ε0,ζ0∈(0,1/2)，令η0:=min{η,ε0}，γ0:=min{γ,μ0}，任意初始点x0∈Rn。令令令k:=0。
步骤2 如果f(zk)=0，那么算法结束。否则，求解下面方程组：
(6)
得下降方向Δzk=(Δμk,Δεk,Δxk)∈Rn+2，其中
步骤3 设λk为1,δ,δ2,…中满足以下不等式的最大值：
f(zk+λkΔzk)≤[1-2σ(1-γk-ηk-ζk)λk]f(zk)。
(7)
步骤4 令转步骤2。
注1 算法1中若ζk=0，则算法1退化为文献[1]中的正则化算法。
定理1 算法1适定，且对于任意的k>0，算法1迭代生成的无限序列{zk=(μk,εk,xk)}中非负序列{μk}和{εk}严格单调递减。
证明 若μk>0,εk>0，由引理1知矩阵H′(zk)非奇异，所以算法1步骤3在第k次迭代中是适定的。
对于任意的α∈(0,1]，定义函数：ϑ(α):=f(zk+λkΔzk)-f(zk)-2αH(zk)TH′(zk)Δzk。
由式(6)可知Δμk=-μk+γkμ0,Δεk=-εk+ηkε0，那么对于任意的λk∈(0,1]，有
εk+1=εk+λkΔεk=εk+λk(-εk+ηkε0)=(1-λk)εk+λkηkε0>0，
(8)
且
μk+1=μk+λkΔμk=μk+λk(-μk+γkμ0)=(1-λk)μk+λkγkμ0>0。
(9)
结合式(5)以及引理1可知函数f(·)关于zk连续可微，那么对于任意的α∈(0,1]，有：
f(zk+λkΔzk)-f(zk)=ϑ
ο(α)≤-2αf(zk)+2αγkf(zk)+2αηkf(zk)+2αζkf(zk)+ο(α)。
这表明存在常数使得f(zk+αΔzk)≤[1-2σ(1-γk0ηk-ζk)α]f(zk)对于任意的都成立。那么，算法1步骤3在第k次迭代是适定的。另外，由式(8)、式(9)及γk、ηk的定义知，对于任意的λk∈(0,1]，有0<μk+1=μk+λkΔμk=μk+λk(-μk+γkμ0)=(1-λk)μk+λkγkμ0<(1-λk/2)μk<μk，以及0<εk+1=εk+λkΔεk=εk+λk(-εk+ηkε0)=(1-λk)εk+λkηkε0<(1-λk/2)εk<εk。证毕。
2 收敛性分析
本节讨论算法1的收敛性。为了建立算法1的全局收敛性，首先给出下面的假设。
假设1 NCP(F)的解集S={x∈Rn|x≥0,F(x)≥0,xTF(x)=0}非空有界。
定理2[1](Moumtain Pass定理) 假设h:Rn→R连续可微且满足强制性。C⊂Rn是一个非空紧集，m是函数h在非空紧集C的边界上的最小值：如果存在两个点a∈C,b∉C，使得h(a)<m,h(
b)<m成立，那么，一定存在一个点c∈Rn满足f(c)=0,f(c)≥0。
定理3 设函数F为连续可微的P0函数，Γ由式(3)定义。设无穷序列{μk},{εk},{αk}满足：其中k≥0,μk>0,εk>0,αk>0。且对于任意的k≥0，{xk}∈Rn，有 若假设1成立，那么序列{xk}有界。
证明 见参考文献[2]定理1.2。
定理4 设函数F为连续可微的P0函数，序列{zk}由算法1迭代生成。若假设1成立，那么:序列{zk}有界，则至少存在一个聚点z*，使得H(z*)=0；ⅲ)序列{zk}的每一个聚点都是NCP(F)的解。
证明 由算法1知ζ0∈(0,1/2)，对于每个那么，对于任意的k>0，有0≤ζk≤ζ0/2k，所以有
ⅰ)由式(7)以及定理1易知序列{f(zk)}单调递减有下界。另一方面，由定理1可得序列{μk}和{εk}也单调递减有下界。那么，当k→∞时，f(zk)→f(z*),μk→μ*,γk→γ*,εk→ε*,ηk→η*。若f(z*)=0，则结论ⅰ)成立。反设f(z*)>0。那么由算法1的步骤3可得
f(zk+δk-1Δzk)>[1-2σ(1-γk-ηk-ζk)δk-1]f(zk)。
(10)
令式(10)中两边k→∞，那么得
H(z*)TH′(z*)Δz*≥-σ(1-γ*-η*)f(z*)。
(11)
再令式(6)两边k→∞，那么得所以，
-f(z*)+γ*f(z*)+η*f(z*)。
(12)
由式(11)和式(12)得-σ(1-γ*-η*)≤-(1-γ*-η*)，即(1-σ)(1-γ*-η*)≤0，与σ<1/2，γ*<μ0<1/2，η*<ε0<1/2矛盾。那么f(z*)=0，ε*=0，μ*=0，即
正则化解决什么问题

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。