Further Applications of a Splitting Algorithm to D

April28,1989LIDS-P-1866FurtherApplicationsofaSplittingAlgorithmtoDecompositioninVariationalInequalitiesandConvexProgramming*PaulTsengtAbstractAclassicalmethodforsolvingthevariationalinequalityproblemistheprojectionalgorithm.WeshowthatexistingconvergenceresultsforthisalgorithmfollowfromonegivenbyGabayforasplittingalgorithmforfindingazeroofthesumoftwomaximalmonotoneoperators.Moreover,weextendtheprojectionalgorithmtosolveanymonotoneaffinevariationalinequalityproblem.Whenappliedtolinearcomplementarityproblems,weobtainamatrixsplittingalgorithmthatissimpleand,forlinear/quadraticprograms,massivelyparallelizable.Unlikeexistingmatrixsplittingalgorithms,thisalgorithmconvergesundernoadditionalassumptionontheproblem.Whenappliedtogeneralizedlinear/quadraticprograms,weobtainadecompositionmethodthat,unlikeexistingdecompositionmethods,cansimultaneouslydualizethelinearconstraintsanddiagonalizethecostfunction.Thismethodgivesrisetohighlyparallelizablealgorithmsforsolvingaproblemofdeterministiccontrolindiscretetimeandforcomputingtheorthogonalprojectionontotheintersectionofconvexsets.KEYWORDS:variationalinequality,operatorsplitting,decomposition,linearcomplementarity,linear/quadraticprogramming.*ThisresearchispartiallysupportedbytheU.S.ArmyResearchOffice,contractDAAL03-86-K-0171(CenterforIntelligentControlSystems),andbytheNationalScienceFoundationundergrantNSF-ECS-8519058.tTheauthoriswiththeLaboratoryforInformationandDecisionSystems,MassachusettsInstituteofTechnology,Cambridge,MA02139.21.IntroductionLetXbeanonemptyclosedconvexsetin39nandletf:X-49nbeacontinuousfunction.Considerthefollowingproblem:Findanx*eXsatisfying(f(x*),x-x*)20,VxeX.VI(X,f)Thisproblem,calledthevariationalinequalityproblem,hasnumerousapplicationstooptimization,includingthesolutionofsystemsofequations,constrainedandunconstrainedoptimization,trafficassignment,andsaddlepointpointproblems.[Seeforexample[Aus76],[BeT89],[CGL80],[GLT81],[KiS80].]WemakethefollowingstandingassumptionsregardingfandX:AssumptionA:(a)Thefunctionfismonotone,i.e.(f(y)-f(x),y-x)0,VxeX,VyeX.(b)TheproblemVI(X,f)hasasolution.LetDbeannxnpositivedefinitematrixD.ConsiderthefollowingalgorithmforsolvingVI(X,f)wherebytheoriginalvariationalinequalityisapproximatedbyasequenceofaffinmevariationalinequalities:AsymmetricProjection(AP)AlgorithmIter.0Startwithanyx°EX.Iter.r+lGivenanxreX,computeanewiteratexT+1Xsatisfying(D(x+l-xr)+f(xr),x-xr+l)0,VxeX.(1.1[Theiteration(1.1)iswelldefinedbecauseDispositivedefinite[BeT89,§3.5],[KiS80,§2].]Wehavecalledtheabovealgorithmtheasymmetricprojection(AP)algorithmbecauseifDissymmetric,thenitreducestothewell-knownprojectionalgorithm[Sib70](alsosee[BeT89],[Daf83],[KiS80],[PaC82])xr+l=argminxX{lix-x+D-lf(xr)llD},r=0,1,2,3where1IllDdenotesthenormIlxllD=(x,Dx)1/2.IthasbeenshownthatifDandfsatisfyacertaincontractioncondition[PaC82],[Daf83],then{xr}generatedbytheAPiteration(1.1)convergestoasolutionofVI(X,f).Unfortunately,thisconditionimpliesthatfisstrictlymonotone,whichexcludesfromconsiderationimportantspecialcasesofVI(X,f)suchaslinearcomplementarityproblemsandlinear/quadraticprograms.Thegoalofthispaperistwo-fold:FirstweshowthattheexistingconvergenceconditionsfortheAPalgorithmfollowasacorollaryofageneralconvergenceconditiongivenbyGabay[Gab83]foraforward-backwardsplittingalgorithm.Thisleadstoaunifiedandamuchsimplercharacterizationoftheconvergenceconditions.Second,weshowthattheconvergenceconditionfortheAPalgorithmcanbebroadenedsuchthatitisapplicabletoallmonotone(notnecessarilystrictlymonotone)affinmevariationalinequalityproblems.Inparticular,weapplythisalgorithmtolinearcomplementarityproblems(forwhichXisthenon-negativeorthant)toobtainamatrixsplittingalgorithmthatissimpleand,forlinear/quadraticprograms,massivelyparallelizable.Unlikeexistingmatrixsplittingalgorithms[Man77],[Pan84],[LiP87],thisalgorithmrequiresnoadditionalassumption(suchassymmetry)ontheproblemdataforconvergence.Wealsoapplythisalgorithmtogeneralizedlinear/quadraticprogrammingproblemstoobtainanewdecompositionmethodforsolvingtheseproblems.Thismethodhastheimportantadvantagethatitcansimultaneouslydualizeanysubsetoftheconstraintsanddiagonalizethecostfunction;henceitishighlyparallelizable.Wedescribeapplicationsofthismethodtoaproblemofdeterministiccontrolindiscretetimeandtocomputingtheorthogonalprojectionontotheintersectionofconvexsets.Thispaperproceedsasfollows:In§2wedescribetheforward-backwardsplittingalgorithmandaconvergenceresultofGabayforthisalgorithm.In§3weshowthattheAPalgorithmisaspecialcaseofthissplittingalgorithmandthatGabay'sresultcontainsasspecialcasesexistingconvergenceresultsfortheAPalgorithm.In§4weshowthattheAPalgorithmcanbeappliedtosolveanymonotoneaffinevariationalinequalityproblem.In§5wefurtherspecializetheAPalgorithmtoadecompositionmethodforgeneralizedlinear/quadraticprogramming.In§6wefurtherspecializetheAPalgorithmtoamatrixsplittingalgorithmforsolvinglinearcomplementarityproblems.Inournotation,allvectorsarecolumnvectorsandsuperscriptTdenotestranspose.Wedenoteby(.,.)theusualEuclideaninnerproductandbyIIIIitsin