一种新的凸二次规划的内点算法第22卷第2期2000年4月湖北三峡学院JOURNALOFHUBEITHREEGORGESUMVERsI1V22No2Apt.2O00一种新的凸二次规划的内点算法张明王浚岭崇超22』(1湖北三峡学院基础学院;f五孺享宜昌郴000;3武汉水利电力大学数理系湖北武汉430072)摘要:提出了一个新的求解凸二次规划的内点算法算法基于原始一对偶仿射尺度算法的思想,每步迭代只须解一个线性方程组,通过适当选取步长,算法具有多项式计算复杂性.关键词:凸二次规划;内点算法;多项式算法中图分类号:o221文献标识码:A文章编号龚睡洲ANewInterior—pointAlgorithmforConvexQuadraticProgrammingZHANGMing-wang,WANGJun.1ing~,HUANGChong—chao3(1.CollegeofBasicCourses;2.DepartmentofMathematics,ScienceandEngineeringColleg eHubeiThreeGorgesUnltersi~y,Yichang443000,China;3DepartmentofMathematicsandP hysics,WuhanUniters盼ofHydraulicandElectricEngineering,WtdzanHuAei430072,China) Abstract:Wedeviseaflewinteriorpointalgorithmforconvexquadraticpwgranmnng.Oural go—tithmonlyrequiresthesolutimofalinearsystemofequationateachstep.Weshowthat,byappr opri-atelychoosingthestepsize,thealgorithmhaspolynomialtimeComplexity. Keywords:Convexquadraticprogramming;Interiorpointalgotlthm;Polgnomialtimealgor ithm.0引言自从1984年kannarkar…的着名算法——梯度投影算法发表以来,由其理论上的多项式收敛性及实际计算的有效性,使得内点算法成为近十多年来优化界研究的热点.通过中外学者的深^研究,线性规划的内点算法已取得了不少成果】_3】.现有内点算法大致可分为三种类型:梯度投影算法,仿射尺度算法和路径跟踪法_3】.仿射尺度算法用简单的仿射变换替代karmarkar原来的投影变换,从而使^们直接解标准形式的线性规划问题.仿射尺度算法的另一特点是结构简单,易于实现,计算效果好但是,算法的收敛性证明十分困难.到目前为止,原始和对偶仿射尺度算法的多项式收敛性还未能证明.1990年,Monteiro等人提供了一种原始一对偶仿射尺度算法并证明了算法酌多项式收敛.收幡日期:1999—09—07基盒瑁目:国家th然科学基金资助项目(69874029j作者简介:张明望(I959一),男,制北宜昌^,湖北三峡学院讲师.硬.从事线性规划与非线性规划的内点算法研究0一(=V第2期张明望等:一种新的凸二次规划的内点算法ll最近,人们已将某些线性规划的内点方法推广应用到凸二次规划.文[7]对线性约束的凸二次规划设计了一种内点算法,算法的每一步迭代,利用内椭球方法的思想(其实质是原始一对偶仿射尺度算法的思想)来近似地求解一个线性规划子问题而得到迭代方向,再通过选取很特殊的内点作为初始内点及适当选取步长使之成为多项式算法.本文基于线性规划的原始一对偶仿射尺度算法的思想,对线性约束的凸二次规划提出了一个新的内点算法,它无需像文[7]那样解一个线性规划子问题便可得到迭代方向,并可证明与文[7]中的迭代方向是一致的.在算法设计及收敛证明中用ll范数替代文[7]中的ll范数,使任一可行内点均可作为初始点,文[7]中对初始点需在"中心线"附近的特殊要求被放松了虽然我们的新算法与文[7]中算法有同样的复杂性,但新算法初始点容易确定,无需解子问题来确定迭代方向,从而使得新算法更简洁,易于实现.另外,收敛性证明也较文[7]简单.1算法的描述本文考虑凸二次规划同题(P)rain)=÷+c(1).￡.Ax:b,x≥O其中A∈R…,bE,cE,QER…为正定或半正定矩阵,(P)的对偶规划为(D)maxd(,Y)=6一_}Q(2).=c+一Ay≥0这里Y∈R,E.设(P)的可行集为s,S'={∈S1>0},W={(,Y,)∈××1∈S,且=c+一Ary>0I,另设s有界,S.≠及m(A):.令=(,Y,s)EW,Aw=(,△y,山)表法迭代方向,基于线性规划原始对偶仿射尺度方法的思想】,我们取它为以下方程组的解:r=0(3.1){一Q△+Ay+As=0(32)【+必s:(3.3)其中X=d(),S=d/ag(),e=(1,…,1)∈R".由以上方程组不难解得Ax=(S+xQ)一'(xArAy+)3y=[A(s+xQ)XA]'.[A(S+如)一'Xs]:=一(Xs—S△)注1令D=(s+郴)一;i,则不难得到=DP^(4)=一(ADAr)'AD(5)其中.=E—DA(D^)加.由此可见.文[7]中通过解线性规划子问题所确定的迭代方向与我们通过解方程组(3.1)一(3.3)所确定的迭代方向一致.算法的迭代步骤:l2湖北三蛱学院第22卷(1)给定,.,取=苦,zoO=(X0,广,)∈,.=(.).,则显然有.厂()一ell≤.,且o.<1.令Ⅳ=【(2.￡一)],口=(1—0~)/2nN,置:=0;(2)如果()<￡,则停止.否则转3);(3)迭代方向△=(血,△),出)由方程组fA△O(6){一Q△x+Ar,~y+△s=o(7)【s+Y:s(8)确定,其中:d(),=d(s).计算"=一,"=一,:'一,¨=+na/l一口,+I=(1～a)Ⅱ^,置:+l转2).注2在算法中,我们用ll范数替代0ll范数是极端重要的.因为对任何可行内点.,按算法中选取,.,总有lff()一.f}≤.但对范数}JJ22一般却没有相应的式子成立.3算法的收敛性为叙述方便,记(,y,s):(,y,s),=u,口=,(,y,s)=(",",5"),i:u".百:0"'.引理1设(,y,)∈妒,(了,j)为下一个迭代点,则(1)=(1一a)+am4s(9)(2)(△)s≥O(10)证由式(8),可得j盂=(一a'2,x)(一n山)=Xis.+a2芦s一口({△+s.):玳十△.凸一gtXi$i=(1一々)曲+口.4x~s这样证明了(1).(△)s:(△)(03x—ATay)=(△)Q3x一(A△)y:(△)rQ3x≥o因此,(2)成立.引理2设",,f∈,u+=I,ⅡTv≥O,则有m(11ull,lII1)≤I1,I1≤÷￡ll(11)'其中U:dlng(1…).证明参见文[3].引理3算法具有性质8ll≤ll4厂≤1其中△:(山:毛,…,,Ax).证由式(8)可得()一:(xs)一(一s△):(xs){.一(xs)一{s△(12)第2期张明望等:一种新的凸二次规捌的内点算法13令D:{s—i1,则上式即为D△+Dl△=()i且(,J△)(D】△s)=()≥0令Ⅱ=,Jr△,=Dl△s,:(XS)寺,则由引理2得l【_l1c川≤韭≤{而IIll≤l_IJ显然,证毕.定理l设(x,y,Z)∈,0E(0,1),I弘一≤舡,o<n<{,百:口+=(1一)则(1)II豆一II≤百.(2)若<1,则,(,y,s)E.证若引理1,可得;.一=(1一a)一+n△一(1一a)=(1一)(一)+△从而由假设及引理3,可得II;一≤(1一n)IIXs—p:ell+nI1≤(1一)llXs一ll+:(rs)≤(1一d)+÷m.(1+≤(1一)舡+№=(1一)[口+]=百这样,(1)得证.由(6)式和(7)式可得;b:c+一A下证>0,j>0.若不然,则存在某个i使得;<0或者'I<0,因为I;;一iI≤一ll≤≤所以因此必有;<0,<0,因为L>0,L>0,L=l—d△,L=L一,所以△>'>0,n△>s>0根据引理3有IA.,;/Z2~S≤I}I≤1于是由假设条件可得l4湖北三蛱学院第22卷詈≥nI4l≥≥(1一日)0+{2≥l与假设条件1>百=0+/1一a矛盾,因此>O,j>0,这就证明了性质(2).由u:(1一)izl;-:(1—)Ⅱ.及()T8<(1+)∞<~2nu,可知算法的迭代次数至多为:I.((2nu.e..]推论设:口一Ⅳ,=(1一n).,=0+m.k/1一,则对所有的:0,1,2….有(i)IXas一e≤u(ii)(,,,5)∈W证因为显然有+,这里0cc{故≤日.+柏2:+一N2加1-0~:1因而由定理1,上述两个结果自然成立定理2算法至多在0(n[(2npe.∈)])ik代后终止.证由于=a一1Ⅳ,=与,故==0(n【{n(2rqz%~t)])注3若取e=2～,则算法与文[7]中算法有相同的计算复杂性0(D.4L),其中L为问题的输入长度.参考文献:j]Karmarkar,N.ANewPols,nonua]～timeAlgorithmfornPmgvammiag~J]co盯lbintnna.t984.4:373—395f21方违诚等线性优化匣扩展,理论匣算i圭[MJ北京:科学出版牡.t994[3]马仲蕃线性规划最新进展[M北京:科学出版杜.i994[4]Monteim.Rc.AGloballyCom'ergemPritrml—dua]InteriorPointAlgorithmCo~v*x嘴[J]MathematicalPrqgrammir,4—1994,64:123—147【5]Sun.jAConverge~Proafforah^ScalingAtgofithmforConv~QIladmfic|u肿B~ithoutNondege~meyAs—sumptlons[O]M日emm】cProgr~ming.199360:69—79r6J‰nteimRCandhider.1andRe~nde.MC^patynomial—timePrimal—dMSea]ingAlgorithmfor1jTleandc…xQⅡadratienamdhsPo~erSeri~Extensioa[j]MathercmtiesofOperalineReseamh.19qO.15:i91 2i4【71坪田德,是方二次规曲l的内椭肆古法j1应甩数学096.9:46～50(责任校对:王太年)。
![基于仿射变换的电力设备红外测温方法及装置[发明专利]](https://img.taocdn.com/s1/m/14d65fa8be1e650e53ea99b9.png)
