资源描述：
《2005 An Interior-Point Method for Semidefinite Programming》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、AnInterior-PointMethodforSemidefiniteProgrammingChristophHelmberg∗FranzRendl†RobertJ.Vanderbei‡HenryWolkowicz§January18,2005PrograminStatistics&OperationsResearchPrincetonUniversityPrinceton,NJ08544January18,2005RevisedOctober1994AbstractWeproposeanewinteriorpointbasedmethodtominimiz
2、ealinearfunctionofamatrixvariablesubjecttolinearequalityandinequalityconstraintsoverthesetofpositivesemidefinitematrices.Weshowthattheapproachisveryefficientforgraphbisectionproblems,suchasmax-cut.Otherapplicationsincludemax-mineigenvalueproblemsandrelaxationsforthestablesetproblem.Key
3、words:semidefiniteprogramming,interior-pointmethods,max-cutrelaxations,max-mineigenvalueproblems.AMS1991SubjectClassification:Primary65F15,Secondary49M35,90C48∗TechnischeUniversit¨atGraz,Institutf¨urMathematik,Kopernikusgasse24,A-8010Graz,Austria.ResearchsupportbyChristianDopplerLabor
4、atoriumf¨urDiskreteOptimierung.†TechnischeUniversit¨atGraz,Institutf¨urMathematik,Kopernikusgasse24,A-8010Graz,Austria.ResearchsupportbyChristianDopplerLaboratoriumf¨urDiskreteOptimierung.‡ResearchsupportbyAFOSRthroughgrantAFOSR-91-0359.§DepartmentofCombinatoricsandOptimization,Univ
5、ersityofWaterloo,Waterloo,Ont.,Canada.ThisauthorthankstheDepartmentofCivilEngineeringandOperationsResearch,PrincetonUniver-sity,fortheirsupportduringhisstaywhileonresearchleave.ThanksalsototheNationalScienceandEngineeringResearchCouncilCanadafortheirsupport.1Introduction.Thecontinuo
6、uslyrisingsuccessofinteriorpointtechniquesappliedtoLinearProgramminghasstimulatedresearchinvariousrelatedfields.Onepossiblelineofgeneralizationconsistsinlookingatlinearprogramsovernon-polyhedralcones.Thistypeofgeneralizationisstudiedinthepresentpaper.Tobespecific,letMndenotethevectors
7、paceofsymmetricn×nmatrices.SupposeA:M7→8、ntsoverpositivesemi
