资源描述：
《1994 Polynomiality of infeasible-interior-point algorithms for linear programming(1994)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、MathematicalProgramming67(1994)109-119Polynomialityofinfeasible-interior-pointalgorithmsforlinearprogramming"ShinjiMizuno*TheInstituteofStatisticalMathematics,4-6-7Minami-Azabu,Minato-ku,Tokyo106,JapanReceived18June1992;revisedmanuscriptreceived7March1994Abstrac
2、tKojima,Megiddo,andMizunoinvestigateaninfeasible-interior-pointalgorithmforsolvingaprimal-dualpairoflinearprogrammingproblemsandtheydemonstrateitsglobalconvergence.Theiralgorithmfindsapproximateoptimalsolutionsofthepairifbothproblemshaveinteriorpoints,andtheydet
3、ectinfeasibilitywhenthesequenceofiteratesdiverges.Zhangprovespolynomial-timecon-vergenceofaninfeasible-interior-pointalgorithmundertheassumptionthatbothprimalanddualproblemshavefeasiblepoints.Inthispaper,weshowthatamodificationoftheKojima-Megiddo-Mizunoalgorithm
4、"solves"thepairofproblemsinpolynomialtimewithoutassumingtheexistenceoftheLPsolution.Furthermore,wedevelopanO(nL)-iterationcomplexityresultforavariantofthealgorithm.Keywords:Polynomial-time;Linearprogramming;Primal-dual;Interior-pointalgorithm1.IntroductionThepri
5、mal-dualinfeasible-interior-pointalgorithmforlinearprogrammingisasimplevariantoftheprimal-dual(feasible)interior-pointalgorithmdevelopedbyMegiddo[7],Kojima,Mizuno,andYoshise[2,3],MonteiroandAdler[9,10],andTanabe[12].Howeverthetheoreticalbehaviorofthealgorithmisn
6、otasweilknownasfortheinterior-pointalgorithm.ThealgorithmhasbeenstudiedbyLustig[4],Lustig,Marsten,andShanno[5],Marsten,Subramanian,Saltzman,Lustig,andShanno[6],Tanabe[13],etc.,andis*Theoriginaltitlewas"PolynomialityoftheKojima-Megiddo-Mizunoinfeasible-interior-p
7、ointalgorithmforlinearprogramming".*ResearchperformedwhilevisitingCornellUniversity(April1992-Januar3,1993)asanOverseasResearchScholaroftheMinistryofScience,EducaüonandCultureofJapan.0025-5610©1994---TheMathematicalProgrammingSociety,Inc.AllrightsreservedSSD1002
8、5-5610(94)00026-P110S.Mizuno/MathematicalProgramming67(1994)109-119knownasoneofthemostefficientinterior-pointalgorithms(seeforexample[5,6]).Kojima,Megiddo,andMizuno[1
