| 求解最大割问题的半定规划松弛的可行方向法 |
| |
| 引用本文： | 穆学文,刘三阳,张亚玲. 求解最大割问题的半定规划松弛的可行方向法[J]. 工程数学学报, 2006, 23(6): 1017-1023 |
| |
| 作者姓名： | 穆学文 刘三阳 张亚玲 |
| |
| 作者单位： | 西安电子科技大学数学系,西安,710071;西安科技大学计算机系,西安,710054 |
| |
| 基金项目： | 教育部跨世纪优秀人才培养计划 |
| |
| 摘 要： | 本文对最大割问题的半定规划松弛提出一个可行方向法,并给出算法的收敛性证明。数值实验表明：与半定规划内点法相比,可行方向法更能有效地求解大规模的最大割问题的半定规划松弛。
|
| 关 键 词： | 最大割 半定规划 可行方向法 内点法 |
| 文章编号： | 1005-3085(2006)06-1017-07 |
| 收稿时间： | 2003-11-24 |
| 修稿时间： | 2003-11-24 |
A Feasible Direction Algorithm for Max-cut SDP Relaxation |
| |
| MU Xue-wen,LIU San-yang,ZHANG Ya-ling. A Feasible Direction Algorithm for Max-cut SDP Relaxation[J]. Chinese Journal of Engineering Mathematics, 2006, 23(6): 1017-1023 |
| |
| Authors: | MU Xue-wen LIU San-yang ZHANG Ya-ling |
| |
| Abstract: | 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. |
| |
| Keywords: | max-cut semidefinite programming feasible direction algorithm interior-point method |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
