English

运筹学学报

• 运筹学 • 上一篇    下一篇

关于半定规划的一种宽邻域不可行内点算法的注记

杨洋, 罗洪林, 罗慧林   

  1. 1. 重庆师范大学数学科学学院, 重庆 401331; 2. 会东中学，四川会东 615200
  • 收稿日期:2015-10-26 出版日期:2016-06-15 发布日期:2016-06-15
  • 通讯作者: 罗洪林 071025013@fudan.edu.cn
  • 基金资助:

    国家自然科学基金(No. 11431004), 重庆市教委科学技术研究项目(No. KJ1500310)

A note on a wide neighborhood infeasible interior-point algorithm for semidefinite programming

YANG Yang, LUO Honglin, LUO Huilin   

  1. 1. School of Mathematical Sciences, Chongqing Normal University, Chongqing 401331, China; 2. Huidong Middle School, Huidong 615200,  Sichuan, China
  • Received:2015-10-26 Online:2016-06-15 Published:2016-06-15

PDF

778

被引次数

2

摘要：

针对半定规划的宽邻域不可行内点算法, 将牛顿法和预估校正法进行结合, 构造出适当的迭代方向, 提出一个修正的半定规划宽邻域不可行内点算法, 并在适当的假设条件下, 证明了该算法具有O(\sqrt{n}L)的迭代复杂界．最后利用Matlab编程, 给出了基于KM方向和NT方向的数值实验结果．

关键词: 半定规划, 宽邻域, 不可行内点算法, 数值分析

Abstract:

Combing Newton method with predictor-corrector method, a new search direction is applied to a wide neighborhood infeasible-interior point algorithm for solving semidefinite programming． It is shown that this algorithm is a polynomial-time algorithm, which requires that all iterative points are in the neighborhood of the infeasible central path, but does not require the feasibility of the initial and iterative points．Under some mild assumptions, we show that the iteration-complexity bound is O(\sqrt{n}L)．Numerical analysis are also presented in this paper．Preliminary numerical results demonstrate the effectiveness of our method in both KM direction and NT direction．

Key words: semidefinite programming, wide neighborhood, infeasible interior-point algorithm, numerical analysis