摘要
针对半定规划的宽邻域不可行内点算法,将牛顿法和预估校正法进行结合,构造出适当的迭代方向,提出一个修正的半定规划宽邻域不可行内点算法,并在适当的假设条件下,证明了该算法具有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.
出处
《运筹学学报》
CSCD
北大核心
2016年第2期79-87,共9页
Operations Research Transactions
基金
国家自然科学基金(No.11431004)
重庆市教委科学技术研究项目(No.KJ1500310)
关键词
半定规划
宽邻域
不可行内点算法
数值分析
semidefinite programming, wide neighborhood, infeasible interior-point algorithm, numerical analysis
