Detecting Infeasibility in Infeasible-Interior-Poi

DetectingInfeasibilityinInfeasible-Interior-PointMethodsforOptimizationM.J.Todd∗January16,2003AbstractWestudyinterior-pointmethodsforoptimizationproblemsinthecaseofinfeasibilityorunboundedness.Whilemanysuchmethodsaredesignedtosearchforoptimalsolutionsevenwhentheydonotexist,weshowthattheycanbeviewedasimplicitlysearchingforwell-definedoptimalsolutionstorelatedproblemswhoseoptimalsolutionsgivecertificatesofinfeasibilityfortheoriginalproblemoritsdual.Ourmaindevelopmentisinthecontextoflinearprogramming,butwealsodiscussextensionstomoregeneralconvexprogrammingproblems.∗SchoolofOperationsResearchandIndustrialEngineering,CornellUniversity,Ithaca,NewYork14853,USA([e-mail]).ThisauthorwassupportedinpartbyNSFthroughgrantDMS-0209457andONRthroughgrantN00014-02-1-0057.11IntroductionThemodernstudyofoptimizationbeganwithG.B.Dantzig’sformulationofthelinearprogrammingproblemandhisdevelopmentofthesimplexmethodin1947.Overthemorethanfivedecadessincethen,thesizesofinstancesthatcouldbehandledgrewfromafewtens(innumbersofvariablesandofconstraints)intothehundredsofthousandsandevenmillions.Duringthesameinterval,manyextensionsweremade,bothtointegerandcombinatorialoptimizationandtononlinearprogramming.Despiteavarietyofproposedalternatives,thesimplexmethodremainedtheworkhorsealgorithmforlinearprogram-ming,evenafteritsnon-polynomialnatureintheworstcasewasrevealed.In1979,L.G.KhachiyanshowedhowtheellipsoidmethodofD.B.YudinandA.S.Nemirovskiicouldbeappliedtoyieldapolynomial-timealgorithmforlinearprogramming,butitwasnotapracticalmethodforlarge-scaleproblems.ThesedevelopmentsarewelldescribedinDantzig’sandSchrijver’sbooks[4,25]andtheeditedcollection[18]onoptimization.In1985,Karmarkar[9]proposedanewpolynomial-timemethodforlinearprogram-mingwhichdidleadtopracticallyusefulalgorithms,andthisledtoaveritableindustryofdevelopingso-calledinterior-pointmethodsforlinearprogrammingproblemsandcertainextensions.Onehighlightwastheintroductionoftheconceptofself-concordantbarrierfunctionsandtheresultingdevelopmentofpolynomial-timeinterior-pointmethodsforalargeclassofconvexnonlinearprogrammingproblemsbyNesterovandNemirovskii[19].Efficientcodesforlinearprogrammingweredeveloped,butatthesametimeconsiderableimprovementstothesimplexmethodweremade,sothatnowbothapproachesareviableforverylarge-scaleinstancesarisinginpractice:seeBixby[3].Theseadvancesarede-scribedforexampleinthebooksofRenegarandS.Wright[24,33]andthesurveyarticlesofM.Wright,Todd,andForsgrenetal.[32,26,27,5].Despitetheirverynicetheoreticalproperties,interior-pointmethodsdonotdealverygracefullywithinfeasibleorunboundedinstances.Thesimplexmethod(afinite,combi-natorialalgorithm)firstdetermineswhetheralinearprogramminginstanceisfeasible:ifnot,itproducesaso-calledcertificateofinfeasibility(seeSection2.4).Thenitdetermineswhethertheinstanceisunbounded(inwhichcaseitgeneratesacertificateofinfeasibilityforthedualproblem,seeSection2),andifnot,producesoptimalsolutionsfortheorig-inalproblem(calledtheprimal)anditsdual.Bycontrast,mostinterior-pointmethods(infiniteiterativealgorithms)assumethattheinstancehasanoptimalsolution:ifnot,theyusuallygiveiteratesthatdivergetoinfinity,fromwhichcertificatesofinfeasibilitycanoftenbeobtained,butwithoutmuchmotivationortheory.Ourgoalistohaveainterior-pointmethodthat,inthecasethatoptimalsolutionsexist,willconvergetosuchsolutions;butifnot,itshouldproduceinthelimitacertificateofinfeasibilityforthepri-malordualproblem.Moreover,thealgorithmshouldachievethisgoalwithoutknowingthestatusoftheoriginalproblem,andinjustone“pass.”Theaimofthispaperistoshowthatinfeasible-interior-pointmethods,whileappar-entlystrivingonlyforoptimalsolutions,canbeviewedintheinfeasibleorunboundedcaseasimplicitlysearchingforcertificatesofinfeasibility.Indeed,undersuitableconditions,the“real”iteratesproducedbysuchanalgorithmcorrespondto“shadow”iteratesthataregeneratedbyanotherinterior-pointmethodappliedtoarelatedlinearprogrammingproblemwhoseoptimalsolutiongivesthedesiredcertificateofinfeasibility.Henceinsomesensethesealgorithmsdoachieveourgoal.Ourmaindevelopmentisinthecontextof2linearprogramming,butwealsodiscussextensionstomoregeneralconvexprogrammingproblems.Section2discusseslinearprogrammingproblems.Wedefinethedualproblem,giveoptimalityconditions,describeagenericprimal-dualfeasible-interior-pointmethod,anddiscusscertificatesofinfeasibility.InSection3,wedescribeaveryattractivetheoreticalapproach(Ye,Todd,andMizuno[35])tohandlinginfeasibilityininterior-pointmethods.Theoriginalproblemanditsdualareembeddedinalargerself-dualproblemwhichalwayshasafeasiblesolution.Moreover,suitableoptimalsolutionsofthelargerproblemcanbeprocessedtoyieldeitheroptimalsolutionstotheoriginalproblemanditsdualoracertificateofinfeasibilitytooneofthese.Thisapproachseemstosatisfyallourgoals,butitdoeshavesomepracticaldisadvantages,whichwediscuss.TheheartofthepaperisSection4,wherewetreatso-calledinfeasible-interior-pointmethods.OurmainresultsareTheorems4.1–4.4,whichrelateaninterior-pointiterationinthe“real”universetooneappliedtoacorrespondingiterateina“shadow”u