资源描述：
《基于sqp与广义投影的线性》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第34卷第11期西南大学学报(自然科学版)2012年11月Vol.34No.11JournalofSouthwestUniversity(NaturalScienceEdition)Nov.2012文章编号:16739868(2012)11000907基于SQP与广义投影的线性互补约束问题全局收敛性算法①朱光军,韦增欣广西大学数学与信息科学学院,南宁530004摘要:利用SQP技术与广义投影相结合得到了带线性互补约束规划问题的一种新算法,在一定的条件下分析和证明了算法的收敛性.该算法的初始点是任意的,不
2、使用罚函数和罚参数.关键词:线性互补约束;SQP;广义投影;全局收敛性中图分类号:O221文献标志码:A带平衡约束的数学规划问题,简称为MPEC问题,其中的约束条件除了不等式和等式约束外,还包含平衡条件,它是一个可变的不等式或带有参数的互补系统.该问题在许多领域(如工程设计,经济平衡等)[1-3]中有广泛的应用.本文考虑的带平衡约束的数学规划问题为如下带线性互补约束的优化问题(LCP):minf(x,y)s.t.Ax≤b,w=Nx+My+q,0≤w⊥y≥0其中:f:Rn+mp×n,N∈Rm×n,M∈Rm
3、×m是给定的矩阵;x∈Rn,y,q∈Rm,b∈Rp→R连续可微;A∈R是给定的向量;w⊥y表示向量w与y正交.文献[1]给出了(LCP)的SQP算法,它要求精确计算w000=Nx+My+q,且满足条件Ax0≤b,这在实际计算时不太容易做到.文献[4]对非线性优化问题提出了SQP技术与广义投影相结合的次可行方向法,其优点是初始点的选择可以任意,每次迭代仅需解一个二次规划,使用广义投影校正得到迭代方向.本文通过互补函数把(LCP)转化为约束优化问题,利用文献[4]的思想对其进行求解,从而得到(LCP)的新算
4、法,该算法在迭代的过程中不使用罚函数,初始点无需满足条件:Ax≤b,w=Nx+My+q.1算法及其性质给出本文使用的记号:z=(x,y,w)s=(x,y)dz=(dx,dy,dw)ds=(dx,dy)kk,yk,wk)skk,yk)dzkk,dyk,dwk),dskk,dyk)z=(x=(x=(dx=(dxTTTA=(a1,…,ap)N=(N1,…,Nm)M=(M1,…,Mm)其中ai,Ni,Mi分别是矩阵A,N,M的行.TTTTjb=(b1,…,bp)q=(q1,…,qm)w=(w1,…,wm)e(j
5、)=(1,…,1)∈R记(LCP)的可行域为F.定义[1]**,y*,w*)∈F称为(LCP)的稳定点,如果满足:点z=(x*,F)⇒▽f(x*,y*)Tdz=(dx,dy,dw)∈T(zds≥0其中:T(z*,F)={d
6、∃zkk*,∃σk*)}为F在向量z*处的切锥.∈F,z→zk>0⇒d=limσk(z-zk→∞①收稿日期:20110218基金项目:国家自然基金资助项目(11161003;11261006).作者简介:朱光军(1965),男,广西平南人,副教授,主要从事优化与管理的研究.2西南大学
7、学报(自然科学版)http://xbbjb.swu.cn第34卷命题1[1]**,w*)≠(0,0),i=1,…,m,则z*是(LCP)的如果z∈F处严格互补条件成立,即(yii稳定点当且仅当存在乘子(u*,v*,λ*)∈R2m+p使下式成立:TTæNöæ0öæAöæ*,y*)▽f(xöçT÷*ç*÷*ç÷*ç÷+ççM÷÷u+ççW÷÷v+çç0÷÷λ=0è0ø*è-IøèYøè0ø**)T(Ax*λ≥0,(λ-b)=0其中:W**),Y**).=diag(wi=diag(yi将(LCP)摄动为:mi
8、nf(x,y)s.t.Ax≤b,w=Nx+My+q(1)μyi≥0wi≥0yiwi=i=1,…,m2其中μ≥0.引入函数:(a,b,)=a+b-a222φμ+b+μ(a,b,μ)∈R×[0,∞)显然对于∀μ>0有æöφ(a,b,μ)=0⇔(a>0)∧(b>0)∧çab=μ÷è2ø则问题(1)可转化为如下问题:minf(x,y)s.t.Ax≤b,w=Nx+My+q(2)(y,w,)=0i=1,…,mφiiμ当μ>0时,问题(2)属于一般非线性规划问题,记问题(2)的可行域为F,令μ(x)=max{0,a}
9、ξix-bii=1,…,pη(z)=max{
10、Nix+Miy+qi-wi
11、}i=1,…,m(y,w,)=max{
12、(y,w,)
13、}ζμφiiμh(z,μ)=ξ(x)+η(z)+ζ(y,w,μ)I(x)={i
14、aix-bi=ξ(x)}J(z)={i
15、Nix+Miy+qi-wi=η(z)}L(y,w,μ)={i
16、φ(yi,wi,μ)=ζ(y,w,μ)}记矩阵C(z,μ)=diag(C1(x),C2(z),C3(y,w,μ)),其中:C1(x)=
