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

A note on a wide neighborhood infeasible interiorpoint algorithm for semidefinite programming

作　　者：杨洋[1] 罗洪林[1] 罗慧林 

机构地区：[1]重庆师范大学数学科学学院,重庆401331 [2]会东中学,四川会东615200

出　　处：《运筹学学报》2016年第2期79-87,共9页Operations Research Transactions

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

摘　　要：针对半定规划的宽邻域不可行内点算法,将牛顿法和预估校正法进行结合,构造出适当的迭代方向,提出一个修正的半定规划宽邻域不可行内点算法,并在适当的假设条件下,证明了该算法具有O(n^(1/3)L)的迭代复杂界.最后利用Matlab编程,给出了基于KM方向和NT方向的数值实验结果.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（√nL）. Numerical analysis are also presented in this paper. Preliminary numerical results demonstrate the effectiveness of our method in both KM direction and NT direction.

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

分 类 号：O221.2[理学—运筹学与控制论]