A unifying investigation of interior--point method

Aunifyinginvestigationofinterior-pointmethodsforconvexprogrammingReport92-89D.denHertogF.JarreC.RoosT.TerlakyTechnischeUniversiteitDelftDelftUniversityofTechnologyFaculteitderTechnischeWiskundeenInformaticaFacultyofTechnicalMathematicsandInformaticsISSN0922-5641Copyrightc1992bytheFacultyofTechnicalMathematicsandInformatics,Delft,TheNetherlands.NopartofthisJournalmaybereproducedinanyform,byprint,photoprint,microfilm,oranyothermeanswithoutpermissionfromtheFacultyofTechnicalMathematicsandInformatics,DelftUniversityofTechnology,TheNetherlands.CopiesofthesereportsmaybeobtainedfromthebureauoftheFacultyofTechnicalMathematicsandInformatics,Julianalaan132,2628BLDelft,phone[phone].AselectionofthesereportsisavailableinPostScriptformattheFaculty’sanonymousftp-site.Theyarelocatedinthedirectory/pub/publications/tech-reportsatftp.twi.tudelft.nlDELFTUNIVERSITYOFTECHNOLOGYREPORT92{89AUNIFYINGINVESTIGATIONOFINTERIORPOINTMETHODSFORCONVEXPROGRAMMINGD.denHertog,F.Jarre,C.Roos,T.TerlakyISSN0922{5641ReportsoftheFacultyofTechnicalMathematicsandInformatics92{89Delft1993iD.denHertog,C.RoosandT.Terlaky,FacultyofTechnicalMathematicsandInformatics,DelftUniversityofTechnology,P.O.Box5031,2600GADelft,TheNetherlands.e{mail:[e-mail]@dutiosa.twi.tudelft.nlF.JarreInstitutfurAngewandteMathematikundStatistik,UniversitatWurzburg,AmHubland,8700Wurzburg,Germany.ThisworkiscompletedwiththesupportofaresearchgrantfromSHELL.ThefourthauthorisonleavefromtheEotvosUniversity,Budapest,andpartiallysupportedbyOTKANo.2116.Copyrightc1993byFacultyofTechnicalMathematicsandInfor-matics,Delft,TheNetherlands.NopartofthisJournalmaybereproducedinanyform,byprint,photoprint,microlmoranyothermeanswithoutwrittenpermis-sionfromFacultyofTechnicalMathematicsandInformatics,DelftUniversityofTechnology,TheNetherlands.iiAbstractIntherecentpastanumberofpaperswerewrittenthatpresentlowcomplexityinterior-pointmethodsfordierentclassesofconvexprograms.Goalofthisarticleistoshowthatthelogarithmicbarrierfunctionassociatedwiththeseprogramsisself-concordant,andthattheanalysesofinterior-pointmethodsfortheseprogramscanthusbereducedtotheanalysisofinterior-pointmethodswithself-concordantbarrierfunctions.Keywords:interior-pointmethod,barrierfunction,dualgeometricprogramming,(extended)en-tropyprogramming,primalandduallp-programming,relativeLipschitzcondition,scaledLipschitzcondition,self-concordance.1IntroductionTheeciencyofabarriermethodforsolvingconvexprogramsstronglydependsonthepropertiesofthebarrierfunctionused.Akeypropertythatissucienttoprovefastconvergenceforbarriermethodsisthepropertyofself-concordanceintroducedin[17].Thisconditionnotonlyallowsaproofofpolynomialconvergence,butnumericalexperimentsin[1,11,14]andothersfurtherindi-catethatnumericalalgorithmsbasedonself-concordantbarrierfunctionsareofpracticalinterestandeectivelyexploitthestructureoftheunderlyingproblem.Awell-knownbarrierfunctionforsolvingconvexprogramsisthelogarithmicbarrierfunction,introducedbyFrisch[4]andFiaccoandMcCormick[3].Todescribethelogarithmicbarrierfunctionmoreprecisely,wewillrstgiveageneralformfortheclassesofproblemsconsideredinthispaper:(CP)8:minf0(x)fi(x)0;i=1;;m;Ax=b;whereAispnmatrixandbanp-dimensionalvector.Thelogarithmicbarrierfunctionforthisprogramisgivenby(x;)=f0(x)mXi=1ln(fi(x));where0isthebarrierparameter.Weshowthatforseveralclassesofconvexproblemsforwhichinterior-pointmethodswerepresentedintheliteraturethelogarithmicbarrierfunctionisself-concordant.Theseclassesare:dualgeometricprogramming,(extended)entropyprogramming,primalandduallp-programming.Sincefordualgeometricprogrammingandduallp-programmingnocomplexityresultsareknownintheliterature,theseself-concordanceproofsenlargetheclassofproblemsforwhichpolynomialitycanbeproved.(In[12]onlyaconvergenceanalysisisgiven.)Moreover,weshowthatsomeothersmoothnessconditionsusedintheliterature(relativeLipschitzcondition[9,7],scaledLipschitzcondition[25,13],MonteiroandAdler’scondition[16])arealsocoveredbythisself-concordancecondition.Theseobservationsallowaunicationoftheanalysesofinterior-pointmethodsforanumberofconvexproblems.Thearticleisdividedinthreeparts.InSection2wegivethedenitionofself-concordanceandstatesomebasiclemmasaboutself-concordantfunctions.InSections3-6weproveself-concordancefortheclassesofproblemstreatedin[5,12,23],andinSection7weshowthatthesmoothnessconditionsusedin[7,9,13,16,25]implyself-concordanceofthebarrierfunction.2SomegeneralcompositionrulesLetusrstgivetheprecisedenitionofself-concordanceasgivenbyNesterovandNemirovsky[17]:Denitionofself-concordance:LetF0beanopenconvexsubsetofIRn.Afunction’:F0!IRiscalled-self-concordantonF0,0,if’isthreetimescontinuouslydierentiableinF0andifforallx2F0andh2IRnthefollowinginequalityholds:r3’(x)[h;h;h]2hTr2’(x)h32;1wherer3’(x)[h;h;h]denotesthethirddierentialof’atxandh.Intuitively,sincer3’describesthechangeinr2’,andsincer3’isboundedbyasuitablepowerofr2’,thisconditionimpliesthattherelativechangeofr2’isboundedby2.Theassociatednormtomeasurethere