搜索
NonlinearOptimizationandApplications2,pp.1-000G.DiPilloandF.Giannessi,Editorsc 1998KluwerAcademicPublishersB.V.ErrorBoundsandSuperlinearConvergenceAnalysisofSomeNewton-TypeMethodsinOptimizationPaulTseng(tseng@math.washington.edu)DepartmentofMathematics,Box354350UniversityofWashington,Seattle,WA98195-4350,U.S.A.AbstractWeshowthat,forsomeNewton-typemethodssuchasprimal-dualinterior-pointpathfollowingmethodsandChen-Mangasariansmoothingmethods,lo-calsuperlinearconvergencecanbeshownwithoutassumingthesolutionsareisolated.Theanalysisisbasedonlocalerrorboundsonthedistancefromtheiteratestothesolutionset.Keywords:Errorbound,superlinearconvergence,Newtonmethod,continua-tion/smoothingmethod,interior-pointmethod.ThisresearchissupportedbyNationalScienceFoundationGrantCCR-9731273.1IntroductionWeconsiderthecomplementarityproblem(CP)of ndingan(x;y)2n nsatis-fyingx 0;y 0;xTy=0;F(x) y=0;(1)whereF=(F1;:::;Fn)Tisacontinuousmappingfromn(orn+)tonthatiscontinuouslydi erentiableonn(orn++)[10,12,26].WedenotebySthesetofofsolutionsofCP,i.e.,S:=f(x;y)2n n:(x;y)satisfy(1)g,whichweassumeisnonempty.AnimportantspecialcaseiswhenFisa ne,givingrisetoalinearCP(LCP)[11,20].Anotherimportantspecialcaseiswhenx= uv ;F(x)=rf0(u)+Pmi=1virfi(u) fi(u)mi=1#;1wheref0;f1;:::;fmaretwicecontinuouslydi erentiablefunctionsde nedonl(orl++),m 0;l 1.Inthiscase,(1)isequivalenttotheKarush-Kuhn-Tuckerconditionassociatedwiththenonlinearprogramminimizef0(u)subjecttou 0;fi(u) 0;i=1;:::;m:Moreover,iff0;f1;:::;fmareconvex(respectively,quadratic)ontheirrespectivedo-mains,thenthisFismonotone(respectively,a ne)andcontinuousonl+m+.AmongthevariousapproachesforsolvingCP,onethathasreceivedmuchat-tentionconcernsNewton-typemethodsbasedoncontinuation/smoothing.Inthisapproach,onechoosesacontinuouslydi erentiablemappingH from2n(or2n++)to2n,parameterizedby 2++,havingthepropertythatH (x;y)!0;(x;y; )!( x; y;0)=)( x; y)2S:Then,fromaninitial andaninitialguess(x;y)ofthesolution,(x;y)isupdatedbymovingitalongaNewtondirectionfortheequatonH (x;y)=0andafterwards isdecreased.Terminationoccurswhen issu cientlysmall.OnechoiceoftheNewtondirectionisthesolution(u;v)22noftheNewtonequationH0 (x;y) uv +H (x;y)=0;(2)whichisusefulinachievingglobalconvergence.Asecondchoice,usefulforpracticale ciencyaswellasachievinglocalsuperlinearconvergence,isthesolution(u;v)ofthemodi edNewtonequationH0 (x;y) uv +H0(x;y)=0;(3)whereH0(x;y)=lim !0H (x;y),assumingthispoint-wiselimitexists.Thetwodirections(2)and(3)maybeusedinseries(i.e.,use(2)toupdate(x;y)andthenuse(3)tofurtherupdate(x;y))orinparallel(i.e.,useaconvexcombinationof(2)and(3)toupdate(x;y)).Primal-dualinterior-pointpathfollowingmethodscorrespondtoH givenbyH (x;y)= (xiyi )ni=1F(x) y ;x0;y0:(4)Theuseofbothdirections(2)and(3)giverisetotheso-calledpredictor-correctormethods.Theliteratureonsuchmethodsisvastand,inthecontextofCP,include[15,18,19,20,21,25,28,29,30,31,33,34,39,42].ThesmoothingmethodofChenandMangasarian[7,8]anditsextensions[3,4,6,9,13,40]correspondtoH givenbyH (x;y)= (xi g((xi yi)= ))ni=1F(x) y ;(5)2whereg:!isanyconvexcontinuouslydi erentiablefunctionwiththepropertiesthatg( )!0andg( ) !0as !1and0g0( )1forall 2.WewilldenotetheclassofsuchfunctionsgbyCM.[Inthecasewheregistwicecontinuouslydi erentiable, g( = )maybewrittenastheintegralR 1R 11 g00( = )d d ,whereg00isinterpretedasaprobabilitydensityfunction.Thisistheformpresentedin[8]andusedbyothers.Theform(5)isfrom[40]andiseasiertouseforouranalysis.]ExamplesofthesmoothingfunctiongincludeoneproposedindependentlybyChenandHarker[5],Kanzow[16],andSmale[32](see[1,2,14,43]andreferencesthereinformethodsbasedonthisg):g( )=(p 2+4+ )=2;(6)andoneobtainedbyintegratingthesigmoidfunction 7!1=(1+e )usedinneuralnetworks[7,8]:g( )=ln(e +1):(7)See[7,8]forotherexamplesofg.Anewexampleofgthatisusefulforouranalysisisg( )=((1=2) +2(1=2 ) = if 0(1=2) +2(1=2+ ) = + if 0;(8)with 0.ForH givenby(5),itiseasilyseenthatH0(x;y)=(minfx;yg;F(x) y).OurfocusisonthelocalsuperlinearconvergenceanalysisoftheprecedingNewton-typemethodsand,forsimplicity,wewillrestrictourattentiontoH givenby(4)and(5).Inthetypicalsuperlinearconvergenceanalysis,thesolutionsneedtobeisolated.Anexceptiontothisistheprimal-dualinterior-pointpredictor-correctormethods,forwhichlocalsuperlinearconvergencecanbeshownforlinearprogramsand,moregenerally,monotoneLCPhavingastrictlycomplementarysolution(see[37,41]andreferencestherein).Furtherextensionsofthisanalysistomonotone(nonlinear)CPandvariationalinequalitieshavebeenobtainedbySunandZhao[34],assuming(inadditiontoexistenceofstrictlycomplementarysolutionandsomemildassumptions)constantrangespaceandcolumnrankofcertainmatricesbasedonF0(x)[34,Assumptions3-4].TherelatedanalysisofRalphandWright[29,30]allowsfornonuniquemultipliers,butwhenspecializedCP,itstillrequiresuniquenessofsolution.MonteiroandZhou[24]improvedtheanalysisof[29]forthecaseoflinearlyconstrainedconvexprogram,assumingconstantnullspaceofcertainmatricesbasedonF0(x).Thisassumptionissimilarto[34,Assumptions3-4]andallowsformultipleprimalsolutions