一类非线性规划问题的信赖域内点算法

《一类非线性规划问题的信赖域内点算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、应用数学MATHEMATICAAPPLICATA2000,13(1):70～74一类非线性规划问题的信赖域内点算法X童小娇　　周叔子(湖南大学数学系,长沙410000)提要:本文对约束为线性的一类非线性优化问题提出了一种信赖域内点算法.其中约束非负性要求通过一个仿射变换阵实现,其子问题变成了一个带仿射变换的线性等式约束的求解.我们证明了算法的有效性,在一定条件下证明了由算法产生的序列收敛到优化问题的一阶稳定点(Kuhn2Tucker点).关键词:非线性优化;内点信赖域算法;收敛性;Kuhn2Tucker点AMS(1991)主题分类:65K05;90C30本文考虑如下约束为

2、线性的非线性优化问题:minf(x),s.tAx=b,x≥0.(1)m×nn1nm其中A∈R(n>m),f(x)∶R→R的连续可微函数为x∈R,b∈R.信赖域算法因其具有较好的可靠性与强适性已成为与传统的线搜索方法并列的两类主要算法之一.对无约束问题、等式约束优化问题的研究已比较成熟;对不等式线性约束问题,大量的算法仍需与有效集方法结合求解(如[1,2,5]中所描述).目前人们开始尝试把传统的内点法与信赖域法结合求解不等式约束优化.界约束优化问题文献[3]中已有较好的结果,对线性等式与非负变量的约束问题(1),文献[4]中给出了一种内点算法,主要借助于Armijo线搜索实

3、现.本文对问题(1)建立了一个纯信赖域内点算法,其算法的特点是:非负性要求由信赖域约束同时控制,这样每个试探步的求解只需解一个带仿射变换的线性等式约束的信赖域子问题,避免了要用有效集解二次规划的问题.本文证明了算法的有效性,且在一定条件下证明了由算法产生的序列收敛到问题(1)的一阶稳定点.3n3m3n问题(1)的一阶稳定条件为(或K2T条件为):存在x∈R,K∈R,u∈R满足:3T33¨f(x)+AK=0,Ax=b,3333uixi=0,i∈In,x≥0,u≥0.(2)3333其中In={1,2,⋯,n},xi,ui分别表示x与u的第i个分量.ndnd定义F={x∈RûA

4、x=b,x≥0},F={x∈RûAx=b,x>0},并设F有界F非空.kk+1kk+1k用x表示第k次求出的点,要求出x点,我们求试探步d,如试探步可接受,则令x=x+kkkd.记Xk=diag(x),即以x的分量为对角元的对角阵,取Bk为对称正定阵,所有范数取为l2kk范数,函数的下标表示在对应点上的值,如fk=f(x),¨fk=¨f(x),其它类似.算法描述如X收稿日期:1999205208©1995-2004TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.第1期童小娇等:一类非线性规划问题的信赖域内点算法71

5、下:0dstep0　给初值x∈F,对称正定阵B0,D∈(0,1),G∈(0,1),00kstep3　若Uk(d)=0,停止计算step4　作下降性测试,计算kkkf(x)-f(x+d)Qk=k,(4)-Uk(d)k-1kkkkk+1kk若Qk

6、修正Bk为Bk+1,k∶=k+1,返step1.kkkkk算法说明:(i)step1中总可找到$,使(3)中的解d满足x+d>0,此因若$<1时,kdi-1kk-1kkk-1kmaxk≤‖Xkd‖≤$<1,则e+Xkd>0,又Xk>0,则x+a=Xk(e+Xkd)xi>0,(此处e为每个分量为1的n维向量).(ii)Bk可由拟牛顿法构造.下面考虑全局收敛性.作如下全局假设:(AS.1)Bk关于k一致有界,即存在常数b>0,使‖Bk‖≤b.2(AS.2)f(x)∈C(F),且存在常数cf>0,使‖¨f(x)‖≤cf.kk引理1Uk(d)=0当且仅当x是原问题的稳定点.kkd

7、k+1m由d是(3)的解,x∈F,则它满足:存在Tk≥0,K∈R,使得下式成立:kTk+1-2kk¨fk+Bkd+AK+TkXkd=0,Ad=0,kT-2kk2kT-2kk2(d)Xkd≤($),Tk≥0,Tk[(d)Xkd-($)]=0,(5)则有kTk1kTkUk(d)=¨fkd+(d)Bkd21kTkkT-2k=-(d)Bkd-Tk(d)Xkd21kTkk2=-(d)Bkd-Tk($).(6)2kkk若Uk(d)=0,由$>0,应有Tk=0,又由Bk的正定性,应有d=0,代入(5)式即有:Tk+1kk¨fk+AK=0,A