求解最大割问题的半定规划松弛的可行方向法  

A Feasible Direction Algorithm for Max-cut SDP Relaxation

作　　者：穆学文[1] 刘三阳[1] 张亚玲[2] 

机构地区：[1]西安电子科技大学数学系,西安710071 [2]西安科技大学计算机系,西安710054

出　　处：《工程数学学报》2006年第6期1017-1023,共7页Chinese Journal of Engineering Mathematics

基　　金：教育部跨世纪优秀人才基金

摘　　要：本文对最大割问题的半定规划松弛提出一个可行方向法,并给出算法的收敛性证明。数值实验表明：与半定规划内点法相比,可行方向法更能有效地求解大规模的最大割问题的半定规划松弛。Based on the semidefinite programming relaxation of the max-cut problem, a feasible direction algorithm is proposed, and its convergence is proved. Numerical experiments show that the proposed algorithm is more efficient than the interior-point algorithm for solving the semidefinite programming relaxation of the max-cut problem.

关 键 词：最大割 半定规划 可行方向法 内点法 

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