1995 Solving linear systems involved in constrained optimization

《1995 Solving linear systems involved in constrained optimization》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、NORTH.HOLLCNDSolvingLinearSystemsInvolvedinConstrainedOptimizationYixunShiDepartmentofMathematics&ComputerScienceBloomsburgUniversityofPennsylvaniaBloomsburg,Pennsylvania17815SubmittedbyRichardA.BrualdiABSTRACTManyinteriorpointmethodsforlargescalelinearprogramming,quadraticpr

2、ogramming,theconvexprogrammingsolvean(n+m)×(n+m)linearsystemineachiteration.Thelastmequationsrequireexactsolutionsinordertomaintainthefeasibility.Currentimplementationsreducethatsteptosolvinganm×mlinearsystem.Thesolutionmustbeexact,becauseotherwisetheerrorwouldbeentirelypasse

3、dontothelastmequationsoftheoriginalsystem.Thismakesthecomputationcostlyandsometimesimpractical.Inthispaper,weproposeaninexpensiveiterativemethodforsolvingthat(n+m)×(n+m)system.Itguaranteesexactsolutionstothelastmequations.Theconvergenceisproved,andtheimplementationalissuesare

4、discussed.Somepreliminarynumericalresultsarealsoreported.1.INTRODUCTIONAn(n+m)X(nXm)linearsystemoftheformDx-ATy=b,(1)Ax=0needstobesolvedineachiterationofmanyinteriorpointmethodsforlargescalelinearprogramming,quadraticprogramming,andconvexprogramming,LINEARALGEBRAANDITSAPPLICA

5、TIONS229:175-189(1995)©ElsevierScienceInc.,19950024-3795/95/$9.50655AvenueoftheAmericas,NewYork,NY10010SSDI0024-3795(94)00007-Z176YIXUNSHIwhereD~Rn×niseitherapositivediagonalmatrixorthesumofapositivediagonalmatrixandasymmetricpositivesemidefinitematrix,A~Rmxn,m

6、,and0=(0,0.....0)T~Rm.ThematricesDandbwillchangeineachiteration,whileA,astheoriginalconstraintmatrix,staysthesame.Toseejustafewexamplesamongmanyothers,welistthefollowingcases.Case1(linearprogramming).Y.Ye(1992)describesaprimal-dualinteriorpointalgorithmforsolvingthelinearprog

7、rammingproblemmincTx(2)s.t.Ax=b,x>~0whereA~Rmxn,mO,andtakeYo~R'~suchthatso=c-AVyo>O.Fork=O,1,2,...untilconvergence,do(i)-(iii).(i)SolveforAxandAyfromthesystem(Xk)-lSkAx-Ar

8、Ay=Ok(Xk)-lpk,(3)AAx=0,whereXk=Diag(xk)isthepositivediagonalmatrixwh