On the behavior of the homogeneous self-dual model

ONTHEBEHAVIOROFTHEHOMOGENEOUSSELF-DUALMODELFORCONICCONVEXOPTIMIZATION1RobertM.Freund2M.I.T.October15,2004AbstractThereisanaturalnormassociatedwithastartingpointofthehomogeneousself-dual(HSD)embeddingmodelforconicconvexoptimization.InthisnormtwomeasuresoftheHSDmodel’sbehaviorarepreciselycontrolledindepen-dentoftheprobleminstance:(i)thesizesofε-optimalsolutions,and(ii)themaximumdistanceofε-optimalsolutionstotheboundaryoftheconeoftheHSDvariables.Thisnormisalsousefulindevelopingastopping-ruletheoryforHSD-basedinterior-pointmethodssuchasSeDuMi.Undermildassumptions,weshowthatastandardstoppingruleimplicitlyinvolvesthesumofthesizesoftheε-optimalprimalanddualsolutions,aswellasthesizeoftheinitialprimalanddualinfeasibilityresiduals.Thistheorysuggestspossiblecriteriafordevelopingstartingpointsforthehomogeneousself-dualmodelthatmightimprovetheresultingsolutiontimeinpractice.AMSSubjectClassification:90C05,90C22,90C25,90C31,90C46,90C51Keywords:ConvexOptimization,ConvexCone,ConicOptimization,Duality,LevelSets,Self-DualEmbedding,Self-scaledCone1ThisresearchhasbeenpartiallysupportedthroughtheMIT-SingaporeAlliance.2MITSloanSchoolofManagement,50MemorialDrive,Cambridge,MA02142-1347,USA.email:[e-mail]SELF-DUALMODEL11PreliminariesWeconsiderconvexoptimizationinconiclinearform:P:VAL∗:=minxcTxs.t.Ax=bx∈C(1)anditsdual:D:VAL∗:=maxy,zbTys.t.ATy+z=cz∈C∗,(2)whereC⊂Xisassumedtobeaclosedconvexconeinthe(finite)n-dimensionallinearvectorspaceX,andbliesinthe(finite)m-dimensionalvectorspaceY.HereC∗isthedualcone:C∗:={z∈X∗|zTx≥0foranyx∈C},whereX∗isthedualspaceofX(thespaceoflinearfunctionalsonX).Wemakethefollowingassumption:AssumptionA:Cisaregularcone(Cisclosed,convex,pointed,andhasnonemptyinterior),wherebyC∗isalsoaregularcone.WesaythatP(D)isstrictlyfeasibleifthereexists¯x∈intC(¯yand¯z∈intC∗)thatisfeasibleforP(D).Following[11](alsosee[10])weconsiderthefollowinghomogeneousself-dual(HSD)embeddingofPandD.Giveninitialvalues(x0,y0,z0)satisfyingx0∈intC,z0∈intC∗,aswellasinitialconstantsτ00,κ00,θ00,definetheproblemH:H:VALH:=minx,y,z,τ,κ,θ¯αθs.t.Ax−bτ+¯bθ=0−ATy+cτ+¯cθ−z=0bTy−cTx+¯gθ−κ=0−¯bTy−¯cTx−¯gτ=−¯αx∈Cτ≥0z∈C∗κ≥0,wheretheconstants¯b,¯c,¯g,and¯αaredefinedasfollows:¯b=bτ0−Ax0θ0¯c=ATy0+z0−cτ0θ0¯g=cTx0−bTy0+κ0θ0¯α=(z0)Tx0+τ0κ0θ0.(3)BEHAVIOROFHOMOGENEOUSSELF-DUALMODEL2NotethattheregularconeassociatedwithHis:KH:=C×C∗×IR+×IR∗+,(4)wherewedistinguishbetweenIR+andIR∗+onlyfornotationalconsistency.BecauseP(D)canberecastequivalentlyastheproblemofminimizingalinearfunctionofa(regular)conevariableovertheintersectionoftheregularconeandanaffineset(see[9],[5]),wewillfocusonthebehavioroftheregularconevariablesxandzandwilleffectivelyignoretheunrestrictedvariablesy.OnenaturalmeasureofofthebehaviorofP/Disthesizeofthelargestε-optimalsolution.Defineforε0:RPε:=maxxxRDε:=maxzz∗s.t.xisfeasibleforPs.t.(y,z)isfeasibleforDcTx≤VAL∗+εbTy≥VAL∗−ε,(5)where·isanygivennorm,andthedualnorm·∗of·is:w∗:=maxv{wTv:v≤1}.ThenRPεisameasureofthebehaviorofP/D:RPεislargetotheextentthatPisnearlyunboundedinobjectivevalue(andtotheextentthatDisnearlyinfeasible),withsimilarremarksaboutRDε.Indeed,Renegar’sdata-perturbationconditionmeasureC(d)mustsatisfyC2(d)+C(d)εc∗≥RPεforε≤c∗;thisfollowsdirectlyfromTheorem1.1andLemma3.2of[7].AcloselyrelatedmeasureofthebehaviorofP/Disthemaximumdistanceofε-optimalsolutionsfromtheboundaryoftheconevariables:rPε:=maxxdist(x,∂C)rDε:=maxzdist∗(z,∂C∗)s.t.xisfeasibleforPs.t.(y,z)isfeasibleforDcTx≤VAL∗+εbTy≥VAL∗−ε,(6)wheredist(x,∂C)denotestheminimaldistancefromxto∂Cinthenorm·anddist∗(z,∂C∗)denotestheminimaldistancefromxto∂C∗inthedualnorm·∗.NotethatrPεmeasuresthelargestdistancetotheboundaryofCamongallε-optimalsolutionsxofP.Inthecontextofinterior-pointmethods,rPεmeasurestheextenttowhichnearoptimal-solutionsarenicelyboundedawayfrom∂C.HereRenegar’sconditionmeasureC(d)mustsatisfyετC3c∗(C2(d)+C(d))≤rPεforε≤c∗,whereτCdenotesthe“min-width”constantofC:τC:=maxx{dist(x,∂C):x∈C,x≤1};BEHAVIOROFHOMOGENEOUSSELF-DUALMODEL3thisfollowsdirectlyfromTheorem1.1of[7]andTheorem17of[4].Itisshownin[3]thatrPεandRDεobeythefollowinginequalitiesandsoarenearlyinverselyproportionalforfixedε0:τC·ε≤rPε·RDε≤2·ε,providedthatrPεandRDεarebothfiniteandpositive,seeTheorem3.2of[3].Thusforagivenε0,itfollowsthatrPεwillbesmallifandonlyifRDεislarge.Theseresultscanalsobestatedindualforms,exchangetherolesoftheprimalanddualproblemsandusingtheappropriatenormsfortheappropriate(regular)conevariables/spaces.Hereinwestudythesizeofthelargestε-optimalsolutionR(·)εandthemax-imumdistanceofε-optimalsolutionsfromtheboundaryoftheconer(·)ε,asappliedtotheHSDmodelH(whichisalsoaconicoptimizationproblemofsimilarconicformatasPand/orD,butwithotherveryspecialstructure).WedenotethesemeasuresforHbyRHεandrHε,respectively.Letw0:=(x0,z0,τ0,κ0)denotethestartingvaluesofthe(regular)conevariablesofH.Ourmainbehavioralresultisthatthereisanaturalnorm·w0definedbyw0anditsregularconeKH(4),andinthisnormthemeasuresRHεandrHεarepreciselycontrolledindependentofanyparticularcharacteristicsoftheprobleminstance,asfollows: