图的最大二等分问题的新型条件梯度算法.pdfVIP

2014年 3月 高 等 学 校 计 算 数 学 学 报 第 36卷第 1期 图的最大二等分问题的新型条件梯度算法 张芳 陈志平 (西安交通大学数学与统计学院计算科学系，西安710049) NEW CONDITIONAL GRADIENT ALGORITHM S FOR THE GRAPH M AX—BISECTION PROBLEM ZhangFang ChenZhiping (DepartmentofComputingScience，SchoolofMathematicsandStatistics，Xi’an JiaotongUniversity，Xi’an710049) Abstract Duetoitswideapplicationareasand intractability，thegraphmax— bisectionDroblem isnow ahottopicincombinatorialoptim ization．Inthispaper， new continuationrelaxationmodelsforthegraphmax—bisectionproblem havebeen proposedbyusingtheadvantagesofthesem idefiniteprogramm ingrelaxationand therank—tworelaxation．Afterstudyingtheoreticalpropertiesofourcontinuation relaxation models，two difierentdescentdirectionsareconstructed，derivedfrom which aretwo new conditionalgradientalgorithmsforsolving the graph max- bisection Droblem ．W ehaveestablished theconvergenceand finitetermination propertiesofrtheproposedalgorithms． Extensivenumericalexperimentsshow that，comparedwithexistingalgorithms，ournew algorithmscannotonlyquickly find betterapproximatesolutions，butalsoefficiently solvethelarge—scalegraph max—bisectionproblems． Kev WOrds graph max—bisection problem ，semidefiniteprograms，conditional gradientalgorithm ，descentdirection，convexconstraint- AMS(2000)subjectclassifications 90C27，90C59 中图法分类号 0221．2 国家自然科学基金 71371152)和西安交通大学基本科研业务费自由 探索类项目资助． 收稿 日期：2010—02—09． 2014年 3月 高 等 学 校 计 算 数 学 学 报 ．87 1 引 言 给定无向图G= (E)，其中V={1，2，… ，几)为 G的节点集合，E为 G的边集合． 如果 (i，J)∈E，定义在此边上的非负权值为 wij=wji，否则 wij=0，对称的权值矩阵记 为W =(Wi) ．图的最大二等分问题就是把给定的无向赋权图G的节点分成个数相同 的两部分 s和 雪= ＼s(这意味着无向图G节点的个数 仃必须是偶数)，使得两节点分别