资源描述：
《On the finite convergence of successive SDP relaxation methods》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、ResearchReportsonMathematicalandComputingSciencesSeriesB:OperationsResearchDepartmentofMathematicalandComputingSciencesTokyoInstituteofTechnology2-12-1Oh-Okayama,Meguro-ku,Tokyo152-8552,JapanOntheFiniteConvergenceofSuccessiveSDP?RelaxationMethodsMasakazuKojimaDe
2、partmentofMathematicalandComputingSciencesTokyoInstituteofTechnology2-12-1Oh-Okayama,Meguro-ku,Tokyo152-8552,Japane-mail:kojima@is.titech.ac.jpyLeventTuncelDepartmentofCombinatoricsandOptimizationFacultyofMathematicsUniversityofWaterlooWaterloo,OntarioN2L3G1,Ca
3、nadae-mail:ltuncel@math.uwaterloo.caAugust1999,B-354nAbstract.LetFbeasubsetofthen-dimensionalEuclideanspaceRrepresentedintermsofacompactconvexsubsetCandasetPof nitelyorin nitelymanyquadraticfunctions0FnonRsuchthatF=fx2C:p(x)0(8p()2P)g.Inthispaper,weinvestigate
4、some0Ffundamentalpropertiesrelatedtothe niteconvergenceofthesuccessiveSDP(semide niteprogramming)relaxationmethodproposedbytheauthorsforapproximatingtheconvexhullofF.Keywords:NonconvexQuadraticProgram,FiniteConvergence,Complexity,Semide niteProgramming,GlobalOpt
5、imization,SDPRelaxation,ConvexRelaxation,Lift-and-ProjectProcedure.?ThismanuscriptwasalsoissuedasResearchReport99-36,DepartmentofCombi-natoricsandOptimization,UniversityofWaterloo,Ontario,Canada,August1999.yResearchofthisauthorwassupportedinpartbyagrantfromNSERC
6、andaPREAfromOntario,Canada.1Introduction.nLetFbeacompactsubsetofthen-dimensionalEuclideanspaceRwhichisdescribedinntermsanonemptycompactconvexsubsetCofRandasetofquadraticinequalitiessuch0thatF=fx2C:p(x)0(8p()2P)g;0FnwherePdenotesasetof nitelyorin nitelymanyquad
7、raticfunctionsonR.PcanFFcontainanynonconvexquadraticfunction,sothatthesetFisnonconvexingeneral.ThispaperstudiestheoreticalconvergencepropertiesoftheSCRM(successiveconvexrelaxationmethod)proposedbyKojima-Tuncel[3]forapproximatingc.hull(F),theconvexhullofF.Assumi
8、ngthatacompactconvexrelaxationCofF(i.e.,acompactconvexsetCF)kkhasbeencomputedatthepreviousiteration(orgiveninitiallywhenk=0),wewilloutlineoneiterationoftheSCRM.We rs
