资源描述：
《1999 New Complexity Analysis of the Primal-Dual Newton Method for Linear Optimization》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、AdvancesinComputationalMathematics0(1999)?{?1NewComplexityAnalysisofthePrimal-DualNewtonMethodforLinearOptimizationJ.PengC.RoosandT.TerlakyDelftUniversityofTechnology,FacultyofTechnicalMathematicsandInformatics,P.O.Box5031,2600GADelft,TheNetherlands.E-mail:J.Peng@its.tudelft.nl,C.Roos@its.t
2、udelft.nl,T.Terlaky@its.tudelft.nlWedealwiththeprimal-dualNewtonmethodforlinearoptimization(LO).Nowa-days,thismethodistheworkinghorseinallecientinteriorpointalgorithmsforLO,anditsanalysisisthebasicelementinallpolynomialityproofsofsuchal-gorithms.Atpresentthereisstillagapbetweenthepracticalb
3、ehaviorofthealgorithmsandthetheoreticalperformanceresults,infavorofthepracticalbehav-ior.Thisisespeciallytrueforso-calledlarge-updatemethods.Wepresentsomenewanalysistools,basedonaproximitymeasureintroducedbyJansenetal.,in1994,thatmayhelptoclosethisgap.Thisproximitymeasurehasnotbeenusedinthea
4、nalysisoflarge-updatemethodsbefore.Thenewanalysisdoesnotimprovetheknowncomplexityresultsbutprovidesauni edwayfortheanalysisofbothlarge-updateandsmall-updatemethods.Keywords:Linearoptimization,interior-pointmethod,primal-dualmethod,proximitymeasure,polynomialcomplexity.AMSSubjectclassi cation
5、:AMSSubjectClassi cation:90C051.IntroductionInteriorpointmethods(IPMs)areamongthemoste ectivemethodsforsolvingwideclassesofoptimizationproblems.SincetheseminalworkofKar-markar[9],manyresearchershaveproposedandanalyzedvariousIPMsforLinearOptimization(LO)andnumerousresultshavebeenreported.Fors
6、urvey,werefertorecentbooksonthesubject([22],[26],[28]).Aninterestingfactisthatalmostallknownpolynomial-timevariantsofIPMsusetheso-calledcentralpath[23]ThisresearchissupportedbytheprojectHighPerformanceMethodsforMathematicalOptimizationundertheSWON-grant613-304-200.2/asaguidelinetotheoptimal
7、set,andsomevariantofNewton'smethodisusedtofollowthecentralpathapproximately.Therefore,thetheoreticalanalysisofIPMsconsiststoalargeextentofanalyzingNewton'smethod.Atpresentthereisstillagapbetweenthepracticalbehaviorofthealgorithmsandthetheoreticalpe
