Primal-dual Interior-Point Methods

Interior-PointMethodsFlorianA.PotraandStephenJ.WrightFebruary10,2000AbstractThemoderneraofinterior-pointmethodsdatesto1984,whenKarmarkarproposedhisalgorithmforlinearprogramming.Intheyearssincethen,algorithmsandsoftwareforlinearprogramminghavebecomequitesophisticated,whileextensionstomoregeneralclassesofproblems,suchasconvexquadraticprogramming,semideniteprogramming,andnonconvexandnonlinearproblems,havereachedvaryinglevelsofmaturity.Wereviewsomeofthekeydevelopmentsinthearea,includingcommentsonboththecomplexitytheoryandpracticalalgorithmsforlinearprogramming,semideniteprogramming,monotonelinearcomplementarity,andconvexprogrammingoversetsthatcanbecharacterizedbyself-concordantbarrierfunctions.1IntroductionIntheirsurveyarticle[6],FreundandMizunowroteInterior-pointmethodsinmathematicalprogramminghavebeenthelargestandmostdramaticareaofresearchinoptimizationsincethedevelopmentofthesimplexmethod:::Interior-pointmethodshavepermanentlychangedthelandscapeofmathematicalprogrammingtheory,practiceandcomputation:::.Althoughmostresearchintheareawasdevotedtolinearprogramming,theauthorsclaimedthatsemideniteprogrammingisthemostexcitingdevelopmentinmathematicalprogrammingin1990s.Althoughvariousinterior-pointmethodshadbeenconsideredonewayoranotherfromthe1950’s,andin-vestigatedquiteextensivelyduringthe1960s(FiaccoandMcCormick[5]),itwasthepublicationoftheseminalpaperofKarmarkar[11]thatplacedinterior-pointmethodsatthetopoftheagendaformanyre-searchers.Onthetheoreticalside,subsequentresearchledtoimprovedcomputationalcomplexityboundsforlinearprogramming(LP),quadraticprogramming(QP),linearcomplementarityproblems(LCP)semidef-initeprogramming(SDP)andsomeclassesofconvexprogrammingproblems.Onthecomputationalside,high-qualitysoftwarewaseventuallyproduced,muchofitfreelyavailable.Thegeneralperformanceofcom-putationaltoolsforlinearprogrammingimprovedgreatly,asthesuddenappearanceofcrediblecompetitionspurredsignicantimprovementsinimplementationsofthesimplexmethod.IntherstyearsafterKarmarkar’sinitialpaper,workinlinearprogrammingfocusedonalgorithmsthatworkedwiththeprimalproblem,butweremoreamenabletoimplementationthantheoriginalmethodorthathadbettercomplexitybounds.AparticularlynotablecontributionfromthisperiodwasRenegar’s1algorithm[21],whichusedupperboundsontheoptimalobjectivevaluetoformsuccessivelysmallersubsetsofthefeasibleset,eachcontainingthesolution,andusedNewton’smethodtofollowtheanalyticcentersofthesesubsetstotheprimaloptimum.AnewerawasinauguratedwithMegiddo’spaper[13],originallypresentedin1987,whichdescribedaframeworkforprimal-dualframeworkalgorithms.Theprimal-dualviewpointprovedtobeextremelyproductive.Ityieldednewalgorithmswithinterestingtheoreticalproperties,formedthebasisofthebestpracticalalgorithms,andallowedfortransparentextensionstoconvexprogrammingandlinearcomplementarity.In1989,Mehrotradescribedapracticalalgorithmforlinearprogrammingthatremainsthebasisofmostcurrentsoftware;hisworkappearedin1992[14].Meanwhile,NesterovandNemirovskii[16]weredevelopingthetheoryofself-concordantfunctions,whichallowedalgorithmsbasedontheprimallog-barrierfunctionforlinearprogrammingtobeextendedtowiderclassesofconvexproblems,particularlysemideniteprogrammingandsecond-orderconeprogramming(SOCP).NesterovandTodd[17,18]extendedtheprimal-dualapproachalongsimilarlinestoamorerestrictedclassofconvexproblemsthatstillincludedSDPandSOCP.Otherworkoninterior-pointalgorithmsforSDPs,whichhaveawidevarietyofapplicationsinsuchareasascontrolandstructuraloptimization,wasalreadywelladvancedbythispoint.WorkonthesealgorithmsgainedadditionalimpetuswhenitwasrecognizedthatapproximatesolutionsofNP-hardproblemscouldtherebybeobtainedinpolynomialtime.Wenowoutlinetheremainderofthepaper.Section2discusseslinearprogramming,outliningthepedigreeofthemostimportantalgorithmsandvariouscomputationalissues.InSection3,wediscussextensionstoquadraticprogrammingandlinearcomplementarityproblems,andcomparetheresultingalgorithmswithactive-setmethods.SemideniteprogrammingisthetopicofSection4.Section5containssomeelementsofthetheoryofself-concordantfunctionsandself-scaledcones.Finally,wepresentsomeconclusionsinSection6.Therearemanyotherareasofoptimizationinwhichareasinwhichinterior-pointapproacheshavemadeanimpact,thoughingeneralthestateoftheartislessmaturethanfortheareasmentionedabove.Generalconvexprogrammingproblemsoftheformminxf(x)s.t.gi(x)0;i=1;2;:::;m;(wherefandgi,i=1;2;:::;m,areconvexfunctions)canbesolvedbyextensionsoftheprimal-dualapproachofSection3.Interestingly,itispossibletoprovesuperlinearconvergenceoftheseprimal-dualalgorithmswithoutassuminglinearindependenceoftheactiveconstraintsatthesolution.Thisobservationpromptedrecentworkonimprovingtheconvergencepropertiesofotheralgorithms,notablysequentialquadraticprogramming.Anumberofresearchershaveusedinterior-pointmethodsinalgorithmsforcombinatorialandintegerprogrammingproblems.(Insomecases,theinterior-pointmethodisusedtondaninexactsolutionofrelatedproblemsinwhichtheintegralityconstraintsarerelaxed.)Indecompositionmethodsforlargelinearandconve