| 求解最大割问题的半定规划松驰的序列线性规划方法 |
| |
| 引用本文： | 穆学文,刘三阳,张亚玲.求解最大割问题的半定规划松驰的序列线性规划方法[J].应用数学,2005(Z1). |
| |
| 作者姓名： | 穆学文 刘三阳 张亚玲 |
| |
| 作者单位： | [1]西安电子科技大学数学系 [2]西安科技大学计算机系 陕西西安 [3]陕西西安 |
| |
| 基金项目： | 跨世纪人才培养计划基金资助项目 |
| |
| 摘 要： | 本文基于最大割问题的半定规划松弛,利用矩阵分解的方法给出了与半定规划松弛等价的非线性规划模型,提出一种序列线性规划方法求解该模型.并在适当的条件下,证明了算法的全局收敛性.数值实验表明:序列线性规划方法在时间上要优于半定规划的内点算法.所以序列线性规划方法能更有效地求解大规模的最大割问题的半定规划松弛.
|
| 关 键 词： | 最大割 半定规划松弛 序列线性规划方法 内点法 |
A Successive Linear Programming Method for Max-cut SDP Relaxation |
| |
| MU Xue-wen,LIU San-yang,ZHANG Ya-ling.A Successive Linear Programming Method for Max-cut SDP Relaxation[J].Mathematica Applicata,2005(Z1). |
| |
| Authors: | MU Xue-wen LIU San-yang ZHANG Ya-ling |
| |
| Institution: | MU Xue-wen~1,LIU San-yang~1,ZHANG Ya-ling~2 |
| |
| Abstract: | Based on the semidefinite programming relaxation of max-cut problem,an equivalent nonlinear programming model is given by decomposing the matrix,and a successive linear programming method is proposed to solve the nonlinear programming model.Furthermore,its global convergent result is given in the appropriate condition.The numerical experiments show that the method is superior to the inner point algorithm in the use of time.Therefore,the method is more efficient than the inner point algorithm to solve the semidefinite programming relaxation of max-cut problem with a large scale. |
| |
| Keywords: | Max-cut Semidefinite programming Successive linear programming method The inner point algorithm |
| 本文献已被 CNKI 维普 等数据库收录！ |
