期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

半定规划的割平面算法及其应用 被引量：2

A cut-plane algorithm for semidefinite programmingand its application
在线阅读 下载PDF
导出
摘要 构造了一种割平面法,对半定规划进行线性松弛,然后利用线性规划的解法求解大规模半定规划问题,并证明了这一算法的收敛性.通过在最大割问题中的应用,说明该算法是简便而有效的. A cut plane algorithm for semidefinite programming is presented in this paper, which relaxs the semidefinite programming to a linear programming, thus solving large scale semidefinite programming effeciently. Its covergence is proved. As an application, a numerical example of the Max-cut problme is given.
作者 王新辉 刘三阳 刘红卫
机构地区 西安电子科技大学理学院
出处 《西安电子科技大学学报》 EI CAS CSCD 北大核心 2004年第1期140-142,152,共4页 Journal of Xidian University
基金 陕西省自然科学基金资助项目(2001S105)
关键词 半定规划 割平面算法 线性规划松弛 最大割问题 semidefinite programming cut-plane linear relaxation Max-cut problem
分类号 O221.2 [理学—运筹学与控制论]
  • 相关文献

参考文献6

  • 1刘红卫,徐凤敏,刘三阳.二次背包问题的半定规划松弛[J].西安电子科技大学学报,2001,28(5):638-640. 被引量：4
  • 2Overton M L, Wolkowicz H. Semidefinite Programming[J]. Math Prog, 1997, 77(1): 105-139.
  • 3Alizade F. Interior Point Methods in Semidefinite Programming with Application to Combinatorial Optimization[J]. SIAM J Optim, 1995,5(1): 13-51.
  • 4Helmberg C. Semidefinite Programming for Combinatorial Optimization[A]. Konrad-Zurse-Zentrum fur in Formationstechnik[C]. Berlin[s.n.]: 2000. 71.
  • 5Rendl S F. Solving the Max-cut Problem Using Eigenvalue[J]. Discrete Appl Math, 1995, 62(2) : 249-278.
  • 6Alizsdeh F, Haeberly J P, Nayakkankuppam M V, et al. SDPpack User's Guide 0.9Belal[R]. New York: Courant Institute of Mathematical Science, 1997.

二级参考文献1

共引文献3

同被引文献5

  • 1陈秀宏.非线性凸半定规划的最优性条件[J].淮阴师范学院学报（自然科学版）,2006,5(2):94-98. 被引量：1
  • 2Sivaramakrishnan. k. , Mitchell. J. E. Properties of a Cutting Plane Method for Semidefinite Programming [R]. 2007. http://www. rpi. edu/-mitchj.
  • 3Fang, S. C. An Analytic Center Cutting Plane Method for Solving Semi-Infinite Variational Inequality Problems [J]. Journal of Global Optimization. 2004, 28: 141-152.
  • 4Hanif D. Sherali, Barbara M. P. Fraticelli Enhancing RLT relaxations via a new class of semidefinite cuts [J]. Journal of Global Optimization 22:233 - 261, 2002.
  • 5Elhedhli, S. , Goffin, J.-L. The integration of an interior-point cutting plane melhod within a branch-and-price algorithm. [J]. Math. Program. Ser. A 100: 267-294, 2004.

引证文献2

二级引证文献1

西安电子科技大学学报
2004年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部