资源描述：
《2010 Improved Full-Newton Step O(nL) Infeasible Interior-Point Method for Linear Optimization》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、JOptimTheoryAppl(2010)145:271288DOI10.1007/s10957-009-9634-0ImprovedFull-NewtonStepO(nL)InfeasibleInterior-PointMethodforLinearOptimizationG.Gu·H.Mansouri·M.Zangiabadi·Y.Q.Bai·C.RoosPublishedonline:4November2009©TheAuthor(s)2009.ThisarticleispublishedwithopenaccessatSpringerlink.comAbstractWep
2、resentseveralimprovementsofthefull-Newtonstepinfeasibleinterior-pointmethodforlinearoptimizationintroducedbyRoos(SIAMJ.Optim.16(4):11101136,2006).Eachmainstepofthemethodconsistsofafeasibilitystepandseveralcenteringsteps.Weuseamorenaturalfeasibilitystep,whichtargetstheμ+-centerofthenextpairofpe
3、rturbedproblems.Asforthecenteringsteps,weapplyasharperquadraticconvergenceresult,whichleadstoaslightlywiderneighborhoodforthefeasibilitysteps.Moreover,theanalysisismuchsimplifiedandtheiterationboundisslightlybetter.KeywordsLinearoptimization·Infeasibleinterior-pointmethod·Full-Newtonstep·Homoto
4、pymethodCommunicatedbyFlorianPotra.G.Gu()·C.RoosFacultyofElectricalEngineering,MathematicsandComputerScience,DelftUniversityofTechnology,P.O.Box5031,2600GADelft,Netherlandse-mail:G.Gu@tudelft.nlC.Roose-mail:C.Roos@tudelft.nlH.Mansouri·M.ZangiabadiDepartmentofMathematicalScience,ShahrekordUniv
5、ersity,P.O.Box115,Shahrekord,IranH.Mansourie-mail:H.Mansouri@tudelft.nlM.Zangiabadie-mail:M.Zangiabadi@tudelft.nlY.Q.BaiDepartmentofMathematics,ShanghaiUniversity,Shanghai,200444,Chinae-mail:yqbai@shu.edu.cn272JOptimTheoryAppl(2010)145:2712881IntroductionWeconsiderthelinearoptimization(LO)prob
6、leminthestandardform(P)min{cTx:Ax=b,x≥0},withitsdualproblem(D)max{bTy:ATy+s=c,s≥0}.HereA∈Rm×n,b,y∈Rm,andc,x,s∈Rn.Withoutlossofgenerality,weassumethatrank(A)=m.Thevectorsx,y,sarethevectorsofvariables.In[1],anewinfeasibleinterior-pointmethod(IIPM)isproposedtosolvetheaboveLOproblems.Itdiffersfrom
7、theclassicalIIPMs(e.g.[29])inthatthenewmethodusesonlyfullsteps(insteadofdampedsteps),whichhastheadvantagethatnolinesearchesareneeded.Ourmotivationfortheuseoffull-Newtonstepsisthat,thoughsuchmethodsarelessgreedy,thebestcomplexityresultsf
