On homogeneous methods for the P 0 matrix linear c

OnSmoothingMethodsfortheP0MatrixLinearComplementarityProblemXiaojunChenYinyuYeySchoolofMathematicsDepartmentofManagementSciencesTheUniversityofNewSouthWalesUniversityofIowaSydney2052,AustraliaIowaCity,IA,USAE-mail:[e-mail]-mail:[e-mail]5March1998AbstractInthispaper,weproposeaBig-MsmoothingmethodforsolvingtheP0matrixlinearcomplementarityproblem.Westudythetrajectorydenedbytheaugmentedsmoothingequationsandglobalconvergenceofthemethodun-deranassumptionthattheoriginalP0matrixlinearcomplementarityproblemhasasolution.Keywords.linearcomplementarityproblem,P0matrix,smoothingalgorithm.AMSsubjectclassications.65H10,90C30,90C33.Thisauthor’sworkwassupportedbytheAustralianResearchCouncil.yThisauthorissupportedinpartbyNSFGrantsDMI-9522507andDMS-9703490.121IntroductionInthispaperweconsiderthelinearcomplementarityproblem(LCP)tTs=0;s=Mt+q;andt;s0;whereMisannnP0matrixandqisanndimensionalvector.AmatrixM2RnniscalledaP0matrixifmaxi:ti6=0ti(Mt)i0;forallt2Rn;t6=0:AlinearcomplementarityproblemiscalledaP0matrixLCPifthematrixMisaP0matrix.TheclassoftheP0matrixLCPincludesthemonotoneLCPandthePmatrixLCP.TheP0matrixLCPhasbeenstudiedextensivelyunderadditionalconditions[5,11].AdierentiablefunctiononRniscalledaP0functionifitsJacobianisaP0matrixateverypointinRn.Anonlinearcomplementarityproblem(NCP)iscalledaP0functionNCPiftheinvolvedfunctionisaP0function.Kojima,MegiddoandNoma[10]provedtheexistenceofatrajectoryintheinteriorofthefeasiblesetoftheP0functionNCPundersomeadditionalconditions.Theirresultsinuencedthedevelopmentofinteriorpointmethodsandnon-interiorpointmethods,andledseveralcontinuationmethodsforsolvingP0functionNCP.Recently,FacchineiandKanzow[7]appliedregularizationmethodsforsolvingacontinuouslydierentiableP0functionNCPunderthefollowingassumption.Assumption1.1ThesolutionsetoftheP0functionNCPisnonemptyandbounded.ThisassumptionisweakerthanthatKojima,Megiddo,NomaandYoshiseusedin[10,11].MoreoveritincludesthemonotoneNCPwithaninteriorpoint,andtheP0andR0NCP[5].AfterFacchinei-Kanzow’sencouragingwork,severalalgorithmsandtheoreticalresultsonregularizationmethodsfortheP0functionNCPhavebeendeveloped[14,15,16]underAssumption1.1.Inparticular,RavindranandGowda[15]generalizedtheresultsofFacchineiandKanzow[7]toacontinuousP0functionvariationalinequalityproblemwithboxconstraints.FacchineiandKanzow[7]gaveacounterexampletoshowthatitisnotpossibletoremovetheboundednessassumptionofthesolutionsetforregularizationmethodsforsolvingtheP0matrixLCP,andtheP0functionNCP.Inthispaper,westudya\Big-MsmoothingmethodfortheP0matrixLCPunderthefollowingassumption,whichremovestheboundednessassumptionofthesolutionsetfromAssumption1.1.Assumption1.2TheP0matrixLCPhasasolution.Big-MinteriorpointmethodshavebeenstudiedforsolvingthemonotoneLCP[12].Themethodsaddoneinequality,withapositivenumberastheright-hand-sidebound,toboundthevariablesoftheproblem.Ifthisinequalitycontainsanoriginal3solution,thentheaugmentedproblemhasasolutionanditisalsoasolutiontotheoriginalproblem.Onecanalwayssetsucientlybigsuchthattheinequalitydoescontainasolution,assumingthatitexists.However,thetechniquesusedinBig-Minteriorpointmethodsheavilyrelyonthemonotoneproperty,whichcannotbecarriedoverfromthemonotoneLCPtotheP0matrixLCP.Onedierence,forexample,isthattheexistenceofaninteriorfeasiblepointimpliestheboundedsolutionsetforthemonotoneLCP,butitisnotheldfortheP0matrixLCP.Example1.1M=0B@0100010111CAandq=0B@0011CA:ItisnotdiculttoverifythatMisaP0-matrixandthatthisLCPhasthestrictlyfeasiblepoint(1;1;1;1;1;1)T.However,thesolutionsetoftheLCPcontainstheunboundedline(x1;0;0;0;0;1)Tforallx10.ThegeneralizationofBig-MmethodstotheP0matrixLCPisnontrivial,see[11].InordertomaketheBig-Msmoothpathanditsneighborhoodbebounded,wehavetoslightlydestroytheP0property.Furthermore,incontrastwiththetrajectoryanalysisgivenbyKojima,MegiddoandNoma[10],theexistenceofsucientlyshortcentralpathisnotguaranteedunderAssumption1.2,seeExample2.1.Weusekktodenotekk1:Weuseeforavectorwithallentriesequalto1andIforadiagonalmatrixwithalldiagonalentriesequalto1.2ABig-MsmoothingmodelLetN=0B@Mr0010eT111CA;p=0B@q01CA;wherer=eMeqandn+5issucientlybig.Letx=(t;;)2Rn+2andy=(s;;)2Rn+2.WeconsidertheLCP(N;p)xTy=0;y=Nx+p;andx;y0:Bytheconstructionofthemodel,wehavethefollowinglemma.Lemma2.11.LCP(N;p)hasafeasibleinteriorpointt=e;=1;=1s=e;=1;=(n+2)1:2.If(t;s)isasolutionofLCP(M;q)witheTt,then(t;0;eTt;s;0;0)and(t;0;0;s;0;eTt)4aresolutionsofLCP(N;p).3.IfLCP(N;p)hasasolution,thenineverycomplementaritysolution(t;;;s;;)ofLCP(N;p),(t;s)isasolutionofLCP(M;q),==0and+=eTt,4.ThefeasiblesetofLCP(N;p)isbounded.NoticethatNisnotaP0matrix,sinceNn+2;n+2=1.AlthoughwecaneasilyconstructaP0matrixwhichsatisesResults1{3ofLemma2.1,e.g.setNn+2;n+2=1,theresultingLCPmayhaveaunboundedsolutionset.ItseemstotheauthorsthatitishardtoconstructaBig-MmodelfortheP0matrixLCPwhichhasboththeP0propertyandtheboundednessofthesolutionset.ThiscontrastswiththemonotoneLCP,forwhichwealwayscanconstructaBig-Mmodelhavin