求解线性规划的宽邻域不可行内点算法  

A Wide Neighborhood Infeasible-Interior-Point Method for Linear Programming

作　　者：杨喜美[1] 张因奎 裴永刚[1] 

机构地区：[1]河南师范大学数学与信息科学学院,河南新乡453007

出　　处：《西南大学学报（自然科学版）》2017年第1期92-98,共7页Journal of Southwest University(Natural Science Edition)

基　　金：国家自然科学基金项目(61179040;11501180);中国博士后基金项目(2016M590346);河南师范大学博士启动基金项目(qd14150);河南师范大学青年基金(2014QK03)

摘　　要：提出了一个求解线性规划的不可行内点算法.该算法的特点是:一方面使用了宽邻域,因此数值实验表明具有较好的计算效果;另一方面,通过分析获得它的多项式复杂度为O(n^(1.5)L),这是宽邻域不可行内点算法的最好复杂度.In this paper,we propose a wide neighborhood infeasible-interior-point method for linear programming.The characteristics of the proposed algorithm are as follows：on the one hand,the proposed algorithm is based on a wide neighborhood and has a good calculation results,which is showed by the experiments.On the other hand,by analyzing,we achieve the iteration complexity O（n（1.5）L） for the proposed algorithm,which is the best complexity result for a wide neighborhood infeasible-interior-point method.

关 键 词：线性规划 不可行内点算法 宽邻域 多项式复杂度 

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