运筹学学报 ›› 2014, Vol. 18 ›› Issue (2): 49-58.

• 运筹学 • 上一篇    下一篇

半定规划的一个新的宽邻域非可行内点算法

冯增哲1,*, 张西学1, 刘建波2, 房亮3   

  1. 1. 泰山医学院信息工程学院, 山东泰安 271016, 2. 泰山医学院科研处, 山东泰安 271016, 3. 泰山学院数学与统计学院, 山东泰安 271021
  • 出版日期:2014-06-15 发布日期:2014-06-15
  • 通讯作者: 冯增哲 E-mail:fengzengzhe@163.com
  • 基金资助:

    山东省自然科学基金(No. ZR2013AM017), 山东省高等学校科技计划项目(No. J11LA55)

A new wide neighborhood infeasible interior-point algorithm for semidefinite programming

FENG Zengzhe1,*, ZHANG Xixue1, LIU Jianbo2, FANG Liang3   

  1. 1. College of Information and Engineering, Taishan Medical University, Tai'an 271016, Shandong, China, 2. Department of Scientific Research, Taishan Medical University, Tai'an 271016, Shandong, China, 3. College of Mathematics and Statistics, Taishan University, Tai'an 271021, Shandong, China
  • Online:2014-06-15 Published:2014-06-15

摘要: 基于一种新的宽邻域, 提出一个求解半定规划的新的非可行内点算法. 在适当的假设条件下, 证明了该算法具有较好的迭代复杂界O(\sqrt{n}L), 优于目前此类算法的最好的复杂性O(n\sqrt{n}L), 等同于可行内点算法.

关键词: 半定规划, 非可行内点法, 宽邻域, 迭代复杂界

Abstract: A new infeasible interior-point algorithm for solving semidefinite programming is proposed, based on a new wide neighborhood. Under suitable assumptions, it shows that the algorithm's iterate complexity bound is O(\sqrt{n}L), which is better than the best result O(n\sqrt{n}L) in this class algorithm so far, and is the same as the best known bound of feasible interior point algorithms.

Key words: semidefinite programming, infeasible interior-point algorithm, wide neighborhood, iteration complexity bound

中图分类号: