On the convergence of an inexact primal-dual inter

REPORTSININFORMATICSISSN0333-3590OntheConvergenceofanInexactPrimal–DualInteriorPointMethodforLinearProgrammingVenansiusBaryamureebaTrondSteihaugREPORTNO188March2000DepartmentofInformaticsUNIVERSITYOFBERGENBergen,NorwayThisreporthasURL://:DepartmentofInformatics,UniversityofBergen,Høyteknologisenteret,P.O.Box7800,N-5020Bergen,NorwayOntheConvergenceofanInexactPrimal–DualInteriorPointMethodforLinearProgramming∗[e-mail]@ii.uib.noMarch31,2000DepartmentofInformaticsUniversityofBergenN–5020BergenNorwayAbstractTheinexactprimal-dualinteriorpointmethodwhichisdiscussedinthispaperchoosesanewiteratealonganapproximationtotheNewtondirec-tion.ThemethodistheKojima,Megiddo,andMizunogloballyconvergentinfeasibleinteriorpointalgorithmTheinexactvariationisshowntohavethesameconvergencepropertiesacceptingaresidualinboththeprimalanddualNewtonstepequationalsoforfeasibleiterates.1IntroductionConsidertheprimallinearprogrammingproblemminimizecTxsubjectto:Ax=b,x≥0,(1a)whereAisanm-by-nmatrixoffullrankm,banm-vector,andcann-vector;anditsdualproblemmaximizebTysubjectto:ATy+z=c,z≥0.(1b)Theoptimalityconditionsforthelinearprogrampair(1a)and(1b)aretheKarush-Kuhn-Tucker(KKT)conditions:F(x,y,z)≡Ax−bATy+z−cXZe=0,x≥0,z≥0,(2)whereX=diag(x),Z=diag(z)andeisthevectorofallonesinℜn.Apoint(x,y,x)isinteriorifx0andz0andaninteriorpointisfeasibleifitsatisfiesalltheequalityconstraints,otherwiseitisinfeasible.Aninteriorpointalgorithmsolvesalinearprogrammingproblembygeneratingasequenceofinteriorpointsfromaninitialinteriorpoint.Bellavia[2]provedglobalconvergenceofaninexactinteriorpointmethod.Ito,Kelley,andSachs[8]andIto[7]discussaninexactprimal-dualinteriorpointit-erationforlinearprogramsinfunctionalspaces.MizunoandJarre[13]provedglobalandpolynomial-timeconvergenceofaninfeasibleinteriorpointalgorithm∗Technicalreportnumber188,DepartmentofInformatics,UniversityofBergen1usinginexactcomputation.Portugal,Resende,Veiga,andJudice[15]presentedatruncatedprimal-infeasibledual-feasibleinteriorpointalgorithmforlinearprogram-ming.Portugal,Fernandes,andJudice[14]presentedatruncatedprimal-infeasibledual-feasibleinteriorpointalgorithmforsolvingmonotonelinearcomplementarityproblems.Themethodssuggestedin[8,14,15]haveamajordrawbackofremainingprimal-feasibleoncetheybecomeprimal-feasible.Thusiftheyhappentobecomeprimal-feasiblebeforethecomplementaritygapissignificantlyreduced,satisfyingtheterminationcriterionintheiterativelinearsystemsolveriscomputationallyexpensive.InthispaperwediscusstheconvergencepropertiesofaninexactimplementationoftheinteriorpointmethodbyKojima,Megiddo,andMizuno[9].Thismethodhasbeenstudiedbymanyresearchers[10,11,12]andisknowntobepracticallyefficientamongthenumerousvariationsandextensionsoftheprimal-dualinteriorpointalgorithm.TheinexactcomputationintheinteriorpointmethodsdiscussedinthispaperisinsolvingthelinearsystemcalledtheNewtonstepequation.InSection2weformulatethelinearequationsandaccuracyrequirementsinthelinearequationsonaugmentedandnormalequationsforms.InSection3westatetheinexactinteriorpointvariationofthealgorithmbyKojima,Megiddo,andMizuno[9].Section4discussestheglobalconvergenceresults.Throughoutthispaperweusethefollowingnotation.Foranyvectorx,xkdenotesxatthek-th(interiorpoint)iteration.SimilarlyforanymatrixXorrealnumberη.XkandηkdenotesXandηatthek-thiteration.Wehaveadoptedthenotation(u,v,w)=(uT,vT,wT)Tsoforanyvectorsx∈ℜn,y∈ℜm,(x,y)∈ℜm+n.2InexactComputationTheperturbedKKTconditionsfor(2)withapositiveμisthenonlinearsystemFμ(x,y,z)≡Ax−bATy+z−cXZe−μe=0,x≥0,z≥0.(3)μisreferredtoastheμ-complementarityparameterandthesetoftriples(x,y,z)thatsatisfy(3)forallμ0iscalledthe(primal-dual)centralpath[17].Let(xk,yk,zk)with(xk,zk)0betheiterateatinteriorpointiterationkandconsidertheperturbedKKTcondition(3).Newton’smethoddefinestheequationofdirectionalchange(theNewtonstepequation)F′μk(xk,yk,zk)ΔxkΔykΔzk=−Fμk(xk,yk,zk).(4)Ifthelinearsystemofequationsissolvedapproximately,thenequation(4)hasaresidualerrorrkF′μk(xk,yk,zk)ΔxkΔykΔzk=−Fμk(xk,yk,zk)+rk.(5)Theideabehindinexactinteriorpointalgorithmsistoderiveastoppingcriterionoftheiterativelinearsystemsolversthatminimizesthecomputationaleffortinvolvedincomputingthesearchdirectionsandguaranteeglobalconvergence.2Theresidualwillbepartitionedintotheprimalinfeasibility¯rk,dualinfeasibilityˆrk,anddeviationincomplementarity˜rk,rk=(¯rk,ˆrk,˜rk).AninexactNewtonstepof(5)isananapproximatesolutionoftheNewtonstepequationderivedfrom(2)F′(xk,yk,zk)ΔxkΔykΔzk=−F(xk,yk,zk)+rkg.(6)whererkg=μk00e+rk.sinceF′=F′μandFμ=F−μk(0,0,e).ConsiderafunctionF:ℜn→ℜnsothatF(x∗)=0andFiscontinuouslydifferentiableinaneighborhoodofx∗.Foragivenxk≈x∗theinexactNewtonmethodgeneratesanewiteratexk+1=xk+skwhereskisanapproximatesolutionoftheNewtonstepequationF′(xk)sk=−F(xk).(7)Letrk=F′(xk)sk+