of F (x) = 0, there exists a ball

ConvergenceofNewton’sMethodforSingularSmoothandNonsmoothEquationsUsingAdaptiveOuterInverses1XiaojunChenSchoolofMathematics,UniversityofNewSouthWalesSydney2052,AustraliaZuhairNashedDepartmentofMathematicalSciences,UniversityofDelawareNewark,DE19716,USALiqunQiSchoolofMathematics,UniversityofNewSouthWalesSydney2052,Australia(January1993,RevisedJune1995)ABSTRACT.WepresentalocalconvergenceanalysisofgeneralizedNewtonmeth-odsforsingularsmoothandnonsmoothoperatorequationsusingadaptiveconstructsofouterinverses.WeprovethatforasolutionxofF(x)=0,thereexistsaballS=S(x;r),r0suchthatforanystartingpointx02Sthemethodconvergestoasolutionx2SofF(x)=0,whereisaboundedlinearoperatorthatdependsontheFrechetderivativeofFatx0oronageneralizedJacobianofFatx0.Pointxmaybedierentfromxwhenxisnotanisolatedsolution.Moreover,weprovethattheconvergenceisquadraticiftheoperatorissmooth,andsuperlineariftheoperatorislocallyLipschitz.Theseresultsaresharpinthesensethattheyreduceinthecaseofaninvertiblederivativeorgeneralizedderivativetoearliertheoremswithnoadditionalassumptions.Theresultsareillustratedbyasystemofsmoothequationsandasystemofnonsmoothequations,eachofwhichisequivalenttoanonlinearcomplementarityproblem.Keywords:Newton’smethod,convergencetheory,nonsmoothanalysis,outerin-verses,nonlinearcomplementarityproblems.AMS(MOS)subjectclassication.65J15,65H10,65K10,49M15.Abbreviatedtitle:Newton’smethodforsingularequations1ThisworkissupportedbytheAustralianResearchCouncilandbytheNationalScienceFoun-dationGrantDMS-901526.11.IntroductionLetXandYbeBanachspacesandletL(X;Y)denotethesetofallboundedlinearoperatorsonXintoY.LetF:X!Ybeacontinuousfunction.WeconsiderthenonlinearoperatorequationF(x)=0;x2X:(1:1)WhenX=Y,itiswell-knownthatifFisFrechetdierentiableandF0islocallyLipschitzandinvertibleatasolutionx,thenthereexistsaballS(x;r);r0suchthatforanyx02S(x;r),theNewtonmethodxk+1=xkF0(xk)1F(xk)(1:2)isquadraticallyconvergenttox.See,e.g.,[9,27,34].Inthenonsmoothcase,F0(xk)maynotexist.ThegeneralizedNewtonmethodproposestousegeneralizedJacobiansofFtoplaytheroleofF0intheNewtonmethod(1.2)inthenitedimensionalcase.LetFbealocallyLipschitzianmappingfromRnintoRm.ThenRademacher’stheoremimpliesthatFisalmosteverywheredierentiable.LetDFbethesetwhereFisdierentiable.Denote@BF(x)=flimxi!xxi2DFrF(xi)g:ThegeneralizedJacobianofFatx2RninthesenseofClarke[8]isequaltotheconvexhullof@BF(x),@F(x)=conv@BF(x);whichisanonemptyconvexcompactset.TheNewtonmethodfornonsingularnonsmoothequationsusingthegeneralizedJacobianisdenedbyxk+1=xkV1kF(xk);Vk2@F(xk):(1:3)Alocalsuperlinearconvergencetheoremisgivenin[33],whereitisassumedthatallV2@F(x)arenonsingular.Qi[31]suggestedamodiedversionofmethod(1.3)intheformxk+1=xkV1kF(xk);Vk2@BF(xk)(1:4)andgavealocalsuperlinearconvergencetheoremformethod(1.4).Histheoremreducedthenonsingularityrequirementonallmembersof@F(x)toallmembersof@BF(x).AnothermodicationisaniterationfunctionmethodintroducedbyHan,PangandRangaraj[13]usinganiterationfunctionG(;):RnRn!Rn.IfFhasaone-sideddirectionalderivativeF0(x;d):=limt#0F(x+td)F(x)t(1:5)2andG(x;d)=F0(x;d),avariantoftheiterationfunctionmethodcanbedenedby(solveF(xk)+F0(xk;d)=0;setxk+1=xk+d:(1:6)SeealsoPang[28]andQi[31].Methods(1.2),(1.3),(1.4)and(1.6)areveryuseful,buttheyarenotapplicabletothesingularcase.Ateachstepin(1.2),(1.3)and(1.4),theinverseofaJacobianorageneralizedJacobianisrequired;in(1.6)anonlinearequationissolvedateachstep(inthesingularcase,itmayhavenosolutions).Oftentheinversecannotbeguaranteedtoexist;singularityoccursinmanyapplications.Forexample,weconsiderthenonlinearcomplementarityproblem(NCP):Foragivenf:Rn!Rn,ndx2Rnsuchthatx0;f(x)0andxTf(x)=0:Mangasarian[19]formulatedtheNCPinthecasewhenfisFrechetdierentiableasanequivalentsystemofsmoothequations:^Fi(x)=(fi(x)xi)2fi(x)jfi(x)jxijxij=0;i=1;2;:::;n;(1:7)wheref=(f1;:::;fn)T:Letsgn()=(1;0;1;0;andletijdenotetheKroneckerfunction.ItiseasytoshowthattheJacobianof^F:=(^F1;:::;^Fn)Tatxisgivenby:@^Fi(x)@xj=2fi(x)@fi(x)@xj(1sgn(fi(x)))+2xiij(1sgn(xi))2fi(x)ij2xi@fi(x)@xji;j=1;2;:::;n:TheJacobianr^F(x)issingularwhenthereissomedegeneracy,i.e.xi=fi(x)=0forsomei.TheNCPcanalsobeformulatedasasystemofnonsmoothequations[28]:~F(x)=min(f(x);x)=0;(1:8)wherethe\minoperatordenotesthecomponentwiseminimumoftwovectors.Itishardtoguaranteethatallmembersof@BF(x)arenonsingularwhenthereissomenonsmoothness,i.e.xi=fi(x)andei6=rfi(x)forsomei,whereeiisthei-throwoftheidentitymatrixI2Rnn.3In[5],ChenandQistudiedaparameterizedNewtonmethod:xk+1=xk(Vk+kI)1F(xk);Vx2@BF(xk);wherekisaparametertoensuretheexistenceoftheinverseofVk+kI:Thelocalsuperlinearconvergencetheoremin[5]requiresallV2@BF(x)tobenonsingular.InNewton-likemethodsforsolvingsmoothandnonsmoothequations,e.g.quasi-Newtonmethodsandsplittingmethods,theJacobianisoftenrequiredtobenonsin-gularatasolutionxtowhichthemethodissupposedtoconverge[4,5,6,9,15,16,27,28,32,40].HenceitisinterestingtoknowwhathappenswiththeNewtonmethodswhenF0(x)orsomeV2@BF(x)aresingularatx.Inthiscasethesolutionsetislocallya