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

NEW CONDITIONAL GRADIENT ALGORITHMS FOR THE GRAPH MAX-BISECTION PROBLEM

作　　者：张芳[1] 陈志平[1] 

机构地区：[1]西安交通大学数学与统计学院计算科学系,西安710049

出　　处：《高等学校计算数学学报》2014年第1期86-96,共11页Numerical Mathematics A Journal of Chinese Universities

基　　金：国家自然科学基金(70971109;71371152);西安交通大学基本科研业务费自由探索类项目(08143032)资助

摘　　要：图的最大二等分问题是组合优化中一类非常重要的问题，它在网络优化，工程技术中有着广泛的应用，许多网络问题都可以转化为图的最大二等分问题，例如超大规模集成电路的设计等．由于该问题是NP—hard问题，很难获得其精确解．Due to its wide application areas and intractability, the graph max- bisection problem is now a hot topic in combinatorial optimization. In this paper, new continuation relaxation models for the graph max-bisection problem have been proposed by using the advantages of the semidefinite programming relaxation and the rank-two relaxation. After studying theoretical properties of our continuation relaxation models, two different descent directions are constructed, derived from which are two new conditional gradient algorithms for solving the graph max- bisection problem. We have established the convergence and finite termination properties for the proposed algorithms. Extensive numerical experiments show that, compared with existing algorithms, our new algorithms can not only quickly find better approximate solutions, but also efficiently solve the large-scale graph max-bisection problems.

关 键 词：最大二等分问题 梯度算法 超大规模集成电路 组合优化 网络优化 工程技术 网络问题 精确解 

分 类 号：O221.2[理学—运筹学与控制论]