A pivotal method for affine variational inequaliti

APIVOTALMETHODFORAFFINEVARIATIONALINEQUALITIESMENGLINCAOANDMICHAELC.FERRISAbstract.Weexplainandjustifyapath-followingalgorithmforsolvingtheequationsAC(x)=a,whereAisalineartransformationfromIRntoIRn,CisapolyhedralconvexsubsetofIRn,andACistheassociatednormalmap.WhenACiscoherentlyoriented,weareabletoprovethatthepathfollowingmethodterminatesattheuniquesolutionofAC(x)=a,whichisageneralizationofthewellknownfactthatLemke’smethodterminatesattheuniquesolutionLCP(q;M)whenMisaP{matrix.Otherwise,weidentifytwoclassesofmatriceswhichareanaloguesoftheclassofcopositive{plusandL{matricesinthestudyofthelinearcomplementarityproblem.WethenprovethatouralgorithmprocessesAC(x)=awhenAisthelineartransformationassociatedwithsuchmatrices.Thatis,whenappliedtosuchaproblem,thealgorithmwillndasolutionunlesstheproblemisinfeasibleinawellspeciedsense.1.IntroductionInthispaperweareconcernedwiththeAneVariationalInequalityproblem.Theprob-lemcanbedescribedasfollows.LetCbeapolyhedralsetandletAbealineartransfor-mationfromIRntoIRn.Wewishtondz2CsuchthathA(z)a;yzi0;8y2C:(AVI)Thisproblemhasappearedintheliteratureinseveraldisguises.Therstisthelineargeneralizedequation,thatis02A(z)a+@C(z);(GE)whereC()istheindicatorfunctionofthesetCdenedbyC(z):=8:0ifz2C;1ifz=2CItcanbeeasilyshownthat@C(z)=NC(z),thenormalconetoCatz,ifz2Candisemptyotherwise,andhence(AVI)isequivalentto(GE).ThesolutionsofsuchproblemsariseforexampleinthedeterminationofaNewton{typemethodforgeneralizedequations.Theproblemhasalsobeentermedthelinearstationaryproblemandwereferthereadertotheworkof[13]forseveralmethodsforthesolutionofthisproblemeitheroveraboundedpolyhedronorapointedconvexpolyhedron.Keywordsandphrases.Anevariationalinequality,normalmap,path{following.ThismaterialisbasedonresearchsupportedbytheNationalScienceFoundationGrantCCR{9157632andtheAirForceOceofScienticResearchGrantAFOSR{89{041012MENGLINCAOANDMICHAELC.FERRISInthisworkwewillusethenotionofanormalmapduetoRobinson[11].Thenormalmap,relatingtoafunctionF:IRn!IRnandanon{empty,closed,convexsetC,isdenedasFC(x):=F(C(x))+xC(x)whereC(x)istheprojection(withrespecttotheEuclideannorm)ofxontothesetC.Throughoutthispaper,wewillbeconcernedwithsolvinganenormalmaps,thatis,FAisalinearmap,CisapolyhedralsetandthesolutionxsatisesAC(x)=a(NE)Notethat(NE)isequivalentto(AVI),sinceifAC(x)=a,thenz:=C(x)isasolutionof(AVI).Furthermore,ifzisasolutionof(AVI),thenx:=z+aA(z)satisesAC(x)=a.Weshallusethisequivalencethroughoutthispaperwithoutfurtherreference.Averyfamiliarspecialcaseof(GE)iswhenCKisapolyhedralconvexcone.Thenitiseasytoshowthat(GE)isequivalenttothegeneralizedcomplementarityproblem[7]z2K;A(z)a2KD;hA(z)a;zi=0whereKD:=fzjhz;ki0;8k2KgisthedualconeassociatedwithK.ThepivotaltechniquethatwedescribeherecanbethoughtofasageneralizationofthecomplementarypivotalgorithmduetoLemke[8].Inx2wedescribethetheoreticalalgorithmandapplyseveralresultsofEavesandRobinsontoestablishitsniteterminationforcoherentlyorientednormalmaps.Inx3wecarefullydescribeanimplementationofsuchamethod,undertheassumptionthatCisgivenbyC:=fzjBzb;Hz=hg:Inx4weextendseveralwellknownresultsforlinearcomplementarityproblemstotheanevariationalinequality.Inparticular,wegeneralizethenotionsofcopositive,copositive{plusandL{matricesfromthecomplementarityliteratureandprovethatouralgorithmprocessesvariationalinequalitiesassociatedwithsuchmatrices.Thatis,whenthealgorithmisappliedtosuchaproblem,eitherasolutionisfound,ortheproblemisinfeasibleinawellspeciedsense.Awordaboutournotation.ForanyvectorsxandyinIRn,hx;yiorxTydenotestheinnerproductofxandy,andinthispaper,thesetwonotationsarefreelyinterchangeable.EachmnmatrixArepresentsalinearmapfromIRntoIRm,thesymbolAreferstoeitherthematrixorthelinearmapasdeterminedbythecontext.GivenalinearmapAfromIRntoIRm,foranyXIRn,thesetA(X):=fy2IRmjy=Ax;forsomex2XgiscalledtheimageofXunderA;foranysetYIRm,thesetA1(Y):=fx2IRnjAx2YgisreferredtoastheinverseimageofYunderA.Inparticular,thesetkerA:=A1(f0g)iscalledthekernelofAandthesetimA:=A(IRn)iscalledtheimageofA.Givenanonempty,closed,convexsetCinIRn,recC:=fd2IRnjx+d2C;8x2C;80giscalledtherecessionconeofCandlinC=recCTrecCisthelinealityofC.IfFisafunctionfromIRntoIRn,thenFCrepresentsthenormalmapdenedabove.IfCisapolyhedralconvexset,asubsetGiscalledafaceofCifthereexistsavectorc2IRnsuchthatG=argmaxx2CcTx.APIVOTALMETHODFORAFFINEVARIATIONALINEQUALITIES32.TheoreticalAlgorithmWedescribebrieyatheoreticalalgorithmthatisguaranteedtondasolutioninnitelymanystepswhenthehomeomorphismconditiondevelopedin[11]holds.Thismethodisarealizationofthegeneralpath{followingalgorithmdescribedandjustiedin[3].Inwhatfollowsweusevarioustermsandconceptsthatareexplainedin[3].Relatedmethodsforndingstationarypointsofanefunctionsonpolyhedralsetsaregivenin[4,5].Amoredetaileddescriptionofanimplementationofthemethodisgiveninthex3;herewedealwiththeoreticalconsiderationsunderpinningthemethod.Otherrelatedworkcanbefoundin[1].Inordertoformulatethealgorithm,itisimportanttounderstandtheunderlyinggeometricstructureoftheproblem.Ourapproachreliesh