Global and uniform convergence of subspace correct

MATHEMATICSOFCOMPUTATIONVolume71,Number237,Pages105{124S0025-5718(01)01311-4ArticleelectronicallypublishedonMay11,2001GLOBALANDUNIFORMCONVERGENCEOFSUBSPACECORRECTIONMETHODSFORSOMECONVEXOPTIMIZATIONPROBLEMSXUE{CHENGTAIANDJINCHAOXUAbstract.Thispapergivessomeglobalanduniformconvergenceestimatesforaclassofsubspacecorrection(basedonspacedecomposition)iterativemethodsappliedtosomeunconstrainedconvexoptimizationproblems.Somemultigridanddomaindecompositionmethodsarealsodiscussedasspecialexamplesforsolvingsomenonlinearellipticboundaryvalueproblems.1.IntroductionThispaperisdevotedtoconvergenceanalysisforaclassofiterativemethodsforsolvingsomeconvexoptimizationproblems.Itiswellknownthatsomeiterativemethods,suchasNewton'smethod,canbeproventobegloballyconvergenttocertainconvexoptimizationproblems.Inthispaper,weshallstudytheglobalconvergencepropertyofaclassofiterativemethodsthatincludemultigridanddomaindecompositionmethods.Multigridanddomaindecompositionmethodshavebeenstudiedextensivelyinrecentyearsforlinearpartialdierentialequations.Recentresearch(seeforexample[37])revealsthatmultigridanddomaindecompositionmethodscanbedescribedandanalyzedunderageneralframeworkbasedonspacedecompositionandsubspacecorrection(seealso[3],[11],[27],[15],and[21]).Naturallythereisalsoagreatdealofworkonnonlinearproblems.Someofthesemethodsaremoreorlessstraightforwardextensionsfromtheonesforthelinearproblems,someofthemarebasedonNewton'smethodandthelinearizedproblemsaresolvedbylinearmethods.Ratherthangoingintothedetailsofvariousdierenttechniques,letusjustgiveasampleofreferencesonthesemethods.Fortheworkbasedonthelinearizationapproach,werefertoBankandRose[2],CaiandDryja[4],Rannacher[23],DeuhardandWeiser[8],Xu[38,39],andAxelssonandLayton[1].Fortheworkbasedonmultigridordomaindecompositionwithnonlinearsmoothersornonlinearlocalsolvers,werefertoLions[19],Mandel[20],GelmanandMandel[13],McCormick[21],HackbuschandReusken[16],ReuskenReceivedbytheeditorMarch10,1998and,inrevisedform,September15,1999andMarch24,2000.2000MathematicsSubjectClassication.Primary65N22,65N55,65K10,65J15.Keywordsandphrases.Parallel,multigrid,domaindecomposition,nonlinear,ellipticequa-tion,spacedecomposition,convexoptimization.TheworkoftherstauthorwaspartiallysupportedbytheNorwegianResearchCouncilStrategicInstituteProgramwithinInverseProblemsatRF{RogalandResearch.TheworkofthesecondauthorwaspartiallysupportedbyNSFDMS-9706949NSFACI-9800244,NASANAG2-1236throughPennsylvaniaStateUniversity.c2001AmericanMathematicalSociety105106XUE{CHENGTAIANDJINCHAOXU[24],DryjaandHackbusch[10],Kornhuber[17,18],TaiandEspedal[33],andZou[40].OuralgorithmsbearsomeofthenaturesofthemethodsofMandel[20],Gel-manandMandel[13],McCormick[21],Kornhuber[17,18]inthesensethatwearereducingtheoriginalminimizationproblemintoanumberofsmallerminimizationproblemsandtryingtoguaranteeamonotonedecreasingofthecostfunctional.ThenonlinearapproachofHackbuschandReusken[16]andReusken[24]dierersfromoursandtherateofconvergenceisinsomesenselocal.ThealgorithmofDryjaandHackbusch[10]isthesameasourparallelsubspacecorrectionalgorithm,whichhasalsobeenstudiedearlierin[33,30,28],butourconvergenceresultsarequitedierent.Theconvergenceanalysispresentedhereisvalidformoregeneralprob-lemswhichcanhandlesomenonlineardiusionproblemsevenwhenthenonlineardiusioncoecientisdegenerateorsingular(seeSection5).Theiterativemethodswewillstudyinthispapercanbeviewedasastraight-forwardextensionofthesubspacecorrectioniterativemethodforlinearproblemsasdescribedin[37]inasimilarmannerasin[19,28,33].Ofcourse,invariousspecialapplications(suchasmultigridanddomaindecompositionmethods),thesemethodsareeitheralmostidenticalorverysimilartosomemethodsstudiedintheaforementionedliterature.Themainconcernofthispaperistoestablishsomeglobalanduniformconvergenceestimatesforaclassofsubspacecorrectioniterativemethodsforsomeunconstrainedconvexoptimizationproblems.Someofthetech-niquesusedinthispaperarebasedonearlierworks([28],seealso[29],[30],[31],[32],[22]and[33]).Wewouldliketopointoutthatmostconvergenceestimatesfornonlinearproblemsintheexistingliteratureareasymptoticinthesensethattherateofconvergenceisattainedonlyaftersucientlymanyiterationsortheinitialguessissucientlyclosetotheexactsolution.Buttheconvergenceestimateswewillpresentareuniformandtheyarevalidattheveryrststepofiteration.Thepaperisorganizedasfollows.InSection2,thealgorithmsareproposedinageneralspacedecompositionsetting.Theneededconditionsfortheconvergenceandalsotheconvergencerateanalysisaresuppliedinsubsection2.2.Itisshowninsubsection4.1thattheoverlappingdomaindecompositionisaspacedecompositiontechniqueanditsconvergencedoesnotdependonthemeshsizeandthenumberofsubdomainsincaseapropercoarsemeshisused.Thecorrespondinginterpretationandestimatesformultigridmethodsisgiveninsubsection4.2.Applicationstothenonlinearp-LaplaceequationareconsideredinSection5.2.AnoptimizationproblemandtwosubspacecorrectionmethodsInthissection,weshalldescribeinanabstractfashionageneraloptimizationproblemandtwosubspacecorrectioniterativemethods.Severalapp