On-the-Implementation-of-a-Primal-Dual-Interior-Po

DigitalObjectIdentifier(DOI)10.1007/s10107-004-0559-yMath.Program.,Ser.A106,25–57(2006)AndreasW¨achter·LorenzT.BieglerOntheimplementationofaninterior-pointfilterline-searchalgorithmforlarge-scalenonlinearprogrammingReceived:March12,2004/Accepted:September2,2004Publishedonline:April28,2005–©Springer-Verlag2005Abstract.Wepresentaprimal-dualinterior-pointalgorithmwithafilterline-searchmethodfornonlinearprogramming.Localandglobalconvergencepropertiesofthismethodwereanalyzedinpreviouswork.Hereweprovideacomprehensivedescriptionofthealgorithm,includingthefeasibilityrestorationphaseforthefil-termethod,second-ordercorrections,andinertiacorrectionoftheKKTmatrix.Heuristicsarealsoconsideredthatallowfasterperformance.ThismethodhasbeenimplementedintheIPOPTcode,whichwedemonstrateinadetailednumericalstudybasedon954problemsfromtheCUTErtestset.Anevaluationismadeofseveralline-searchoptions,andacomparisonisprovidedwithtwostate-of-the-artinterior-pointcodesfornonlinearprogramming.Keywords.Nonlinearprogramming–Nonconvexconstrainedoptimization–Filtermethod–Linesearch–Interior-pointmethod–Barriermethod1.IntroductionGrowinginterestinefficientoptimizationmethodshasledtothedevelopmentofinterior-pointorbarriermethodsforlarge-scalenonlinearprogramming.Inparticu-lar,thesemethodsprovideanattractivealternativetoactivesetstrategiesinhandlingproblemswithlargenumbersofinequalityconstraints.Overthepast15years,therehasalsobeenabetterunderstandingoftheconvergencepropertiesofinterior-pointmeth-ods[16]andefficientalgorithmshavebeendevelopedwithdesirableglobalandlocalconvergenceproperties.Toallowconvergencefrompoorstartingpoints,interior-pointmethods,inbothtrustregionandline-searchframeworks,havebeendevelopedthatuseexactpenaltymeritfunctionstoenforceprogresstowardthesolution[2,21,29].Ontheotherhand,FletcherandLeyffer[14]recentlyproposedfiltermethods,offeringanalternativetomeritfunctions,asatooltoguaranteeglobalconvergenceinalgorithmsfornonlinearprogramming.Theunderlyingconceptisthattrialpointsareacceptediftheyimprovetheobjectivefunctionorimprovetheconstraintviolationinsteadofacombinationofthosetwomeasuresdefinedbyameritfunction.Morerecently,thisfilterapproachhasbeenadaptedtobarriermethodsinanumberofways.M.Ulbrich,S.Ulbrich,andVicente[22]consideratrustregionfiltermethodAndreasW¨achter:IBMT.J.WatsonResearchCenter,P.O.Box218,YorktownHeights,NY,10598,USA.e-mail:[e-mail]:CarnegieMellonUniversity,5000ForbesAvenue,Pittsburgh,PA,15213,USA.e-mail:[e-mail]assification(2000):49M37,65K05,90C30,90C5126A.W¨achter,L.T.Bieglerthatbasestheacceptanceoftrialstepsonthenormoftheoptimalityconditions.Also,Benson,Shanno,andVanderbei[1]proposedseveralheuristicsbasedontheideaoffiltermethods,forwhichimprovedefficiencyisreportedcomparedtotheirpreviousmeritfunctionapproach,althoughnoconvergenceanalysisisgiven.Finally,globalcon-vergenceofaninterior-pointalgorithmwithafilterlinesearchisanalyzedin[26].Theassumptionsmadefortheanalysisoftheinterior-pointmethodin[26]arelessrestrictivethanthosemadeforpreviouslyproposedline-searchinterior-pointmethodsfornonlinearprogramming(e.g.,[10,29]).Anumberofinterior-pointmethodshavebeenimplementedinrobustsoftwarecodes(suchas[3,23]),andnumericaltestshaveshownthemtobeefficientandrobustinpractice.Inthispaperwedescribethedetaileddevelopmentofaprimal-dualinterior-pointalgorithmwithafilterline-search,basedontheanalysisin[26].Weconsideraprimal-dualbarriermethodtosolvenonlinearoptimizationproblemsoftheformminx∈Rnf(x)(1a)s.t.c(x)=0(1b)xL≤x≤xU,(1c)wherexL∈[−∞,∞)nandxU∈(−∞,∞]n,withx(i)L≤x(i)U,arethelowerandupperboundsonthevariablesx.Theobjectivefunctionf:Rn−→Randtheequalityconstraintsc:Rn−→Rm,withm≤n,areassumedtobetwicecontinuouslydiffer-entiable.Problemswithgeneralnonlinearinequalityconstraints,“d(x)≤0,”canbereformulatedintheaboveformbyintroducingslackvariables.Thepaperisorganizedasfollows.Section2presentstheoverallalgorithm,includingthestepcomputation,thefilterline-searchprocedure,andasecond-ordercorrection.InSection3,wedescribesomeaspectsofthealgorithm,anditsimplementation,inmoredetail,includingtherestorationphaseforthefilterprocedure,aswellasseveralheu-risticstoimprovetheperformanceoftheoverallmethod.Section4presentsnumericalresultsofourimplementation,calledIPOPT,fortheCUTErtestset[18],includingacomparisonofthefiltermethodwithapenaltyfunctionapproach,andacomparisonwithtwostate-of-the-artnonlinearoptimizationcodes,KNITRO[3,28]andLOQO[23].1.1.NotationThei-thcomponentofavectorv∈Rniswrittenasv(i).Norms·denoteafixedvectornormanditscompatiblematrixnormunlessexplicitlynoted.WefurtherintroducethenotationX:=diag(x)foravectorx(similarlyZ:=diag(z),etc.),andestandsforthevectorofallonesforappropriatedimension.Finally,wewillreferto
machasthemachineprecisionforthefinitearithmetic.Forthecomputerandimplementationusedforournumericalexperiments,itis
mach≈10−16.Thealgorithmpresentedinthispaperhasparameters,whichhavetobegivenvaluesforapracticalimplementation.Exceptwhereexplicitlynoted,theseparametersdonotdependonthedetailsofthefin