图的最大二等分问题的非线性规划算法  

A Nonlinear Programming Algorithm for MAX Bisection

作　　者：穆学文[1] 刘三阳[1] 

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

出　　处：《应用数学》2004年第2期216-219,共4页Mathematica Applicata

基　　金：陕西省自然科学基金资助项目 (2 0 0 1SL0 5 )

摘　　要：基于图的最大二等分问题的半定规划松驰模型 ,本文提出一个非线性规划算法求解该模型 ,得到该半定规划松驰模型的一个次优解 ,并且给出算法的收敛性证明 .Based on the semidefinite programming relaxation of Max Bisection,the paper produce a nonlinear programming algorithm to solve the relaxation,and then a suboptimal solution is obtained.Furthemore,its convergence result is given.The numerical experiment shows that the algorithm can solve the relaxation of Max Bisection effectively.

关 键 词：图论 最大二等分问题 非线性规划 半定规划 LAPLACIAN矩阵 矩阵分解 

分 类 号：O157.5[理学—数学] O221.2[理学—基础数学]