解非线性半定规划的非光滑牛顿型方法的局部和全局收敛性

OnLocalandGlobalConvergenceofaNonsmoothNewton-typeMethodforNonlinearSemide¯nitePrograms¤ChengjinLiyandWenyuSunzAbstractInthispaper,wepresentanonsmoothNewton-typemethodforthesolutionofnonlinearsemide¯niteprograms.Ateachiteration,themethodsolvesasystemofconventionallinearequationswithsomespe-cialelementsofB-subdi®erential.Thismethodisshowntobelocallyquadraticallyconvergentundercertainassumptionsandgloballycon-vergentwithlinesearchandaspecialB-subgradient.Keywords.Nonlinearsemide¯niteprograms,nonsmoothNewton-typemethod,localconvergence,globalconvergence.1.IntroductionInthispaper,weconsiderthenonlinearsemide¯niteprogram(inbrief,nonlinearSDP):minX2Snf(X)s:t:g(X)=0;(1.1)Xº0;wheref:Sn!R;g:Sn!Rmaretwicedi®erentiablefunctions,SndenotesthesubspaceofallsymmetricmatricesinRn£n,andXº0asymmetricpositivesemide¯nitematrix.Iffandgarealllinear(a±ne)functions,the¤ThisworkissupportedbytheNationalNaturalScienceFoundationofChina,theSpe-cializedResearchFundofDoctoralProgramofHighEducationofChina,andtheNaturalScienceFundofJiangsuProvinceofChina.ySchoolofMathematicsandComputerScience,NanjingNormalUniversity,Nanjing210097,China.Email:[e-mail]mputerScience,NanjingNormalUniversity,Nanjing210097,China.Email:[e-mail]1(1.1)reducestoanormallinearSDPproblem,whichhasbeenextensivelystudiedduringthelastdecade,see,e.g.,[8,37,36,33].HoweverresearchworksonthenonlinearSDParemuchmorerecentandstillinitspreliminaryphase,fordetail,pleaserefer[2,7,11,15,5].Usingsomeresultsfromthecorrespondingdualitytheory,itisnotdi±culttoseethat,undermildassumptions,thesemide¯niteprogram(1.1)hasasolutionifandonlyifthefollowingoptimalityconditions(KKTconditions)hold:Df(X)+mXr=1¸rDgr(X)¡S=0;gr(X)=0;r=1;¢¢¢;m;(1.2)Xº0;Sº0;hX;Si=0;where¸=(¸1;¸2;¢¢¢;¸m)2Rm,Df(X)andDgr(X)areF(rechet)-derivativesoffandgratpointXrespectively,andhA;Bi:=trace(AB)denotesthein-nerproductofA;B2Rn£n,kXkFandkbk2representhX;Xi12forallX2Snand(mPr=1b2r)12forallb2Rm,respectively.Thelastequationin(1.2),i.e.hX;Si=0()XS=0forallXº0;Sº0,wherethelatterthree000denotezeromatrixwithproperdimension.Therearemanystandardande±cientmethods,basedonKKTcondi-tions,areusedforsolutionofsemide¯niteprograms,suchasinterior-pointmethod[1,9,14,19,39,32,18],(non)smoothNewtonmethod,etc.Byin-troducingsmoothedFischer-Burmeisterfunction,modi¯edminimumfunctionandsquaredsmoothingfunction,thesmoothingNewton'smethodforsolutionoflinearSDPandnonlinearSDPwasintroducedin[11,30],andKanzowetc.[12]showedthelocallyquadraticconvergenceofanonsmoothNewton-typemethodforlinearSDPwithoutstrictcomplementarity.AllofaboveNewton'smethodsarebaseoncertainequationwiththefunctionsjustbeingintroduced,whichisequivalenttooneofthefollowingconditions:Xº0;Sº0;XS=0;(1.3)orXº0;Sº0;XS=I;(1.4)where0isarealnumberandIdenotestheidenticalmatrixwithappreciatesize.ItiswellknownthatforallX;S2Sn,thefollowingequationisequivalentto(1.3)(pleaserefer[28,38]),PSn+(X¡S)¡X=0;(orPSn+(S¡X)¡S=0;)2£nsymmetricpositivesemide¯nitematricesandPSn+(¢)theorthogonalprojectiononSn+.ThentheKKTconditionscanbereformulatedas£(X;¸;S)=0BB@Df(X)+mPr=1¸rDgr(X)¡Sg(X)PSn+(X¡S)¡X1CCA=0;(1.5)whereg(X)=(g1(X);g2(X);¢¢¢;gm(X)).Itisunknownwhetherbettertheoryorbettercomputationalresultswouldbeobtainedwhenthelasttermin(1.5)isreplacedbyPSn+(S¡X)¡S.DislikeFischer-Burmeisterorminimumfunction,itisnoteasyfororthogo-nalprojectionfunctionPSn+(¢)tobemodi¯edtoowntheequivalencepropertywith(1.4),bywhichtheequation(1.5)canbesolvedbysmoothNewton'smethod.TheaimofthispaperistointroduceanewspecialnonsmoothNewton'smethodforsolutionofnonlinearSDP(1.1)bysolvingtheequa-tion£(X;¸;S)=0,andwealsoestablishthelocallyquadraticconvergenceofthismethodunderdi®erentconditionsandtheglobalconvergenceofthemethodwithlinesearch.Notation:LetY:=(X;¸;S),¢Y:=(¢X;¢¸;¢S),Q:=X¡S,H:=¢X¡¢S,andletY¤beaKKTpointofproblem(1.1).ByA¤,wedenotethelinearoperatorA¤(¢):=0B@hDg1(X¤);¢i...hDgm(X¤);¢i1CA;andletoperator(A¤)zbetheadjointofA¤,so(A¤)z(¸)=mPi=1¸iDgi(X¤),where¸=(¸1;¢¢¢;¸m).AssumethatQ¤hasthefollowingspectraldecompositionQ¤=U¤¤¤(U¤);where¤¤isthethediagonalmatrixwitheigenvalues¸1(Q¤)¸¢¢¢¸¸n(Q¤)ofQ¤asthediagonalelements,andU¤isacorrespondingorthogonalmatrixoforthonormaleigenvectors.ThenPSn+(Q¤)=U¤¤¤+(U¤);(1.6)where¤¤+isthediagonalmatrixwhosediagonalentriesarethenonnegativepartsoftherespectivediagonalentriesof¤¤.Fordetails,pleaserefer[26,10,3].De¯nethreeindexsetsofpositive,zero,andnegativeeigenvaluesofQ¤,respectively,as®¤:=fi:¸i(Q¤)0g;¯¤:=fi:¸i(Q¤)=0g;°¤:=fi:¸i(Q¤)0g;(1.7)andthenumbersofabovethreeindexsetsaredenotedbyj®¤j,j¯¤jandj°¤j,respectively.Write¤¤=0@¤®¤0000000¤°¤1AandU¤=[U®¤U¯¤U°¤]withU®¤2Rn£j®¤j;U¯¤2Rn£j¯¤j,andU°¤2Rn£j°¤j.De¯nej®¤j£j°¤jmatrix¦¤as¦¤ij:=¸i(Q¤)¸i(Q¤)¡¸j®¤j+j¯¤j+j(Q¤);forall1·i·j®¤j;1·j·j°¤j:TheothernotationsAk;(Ak)z;Qk;Uk;¤k;¦k;®k;¯k;°k;j®kj;j¯kj;j°kj;¤®k;¤°k,U®k;U¯kandU°karecorrespondingnotationsforcurrentiterateYkin-steadofoptimalpointY¤.inaddition,we