修正一类非单调线性互补问题的宽邻域路径跟踪算法  

Modifications of a Wide-neighborhood Path-following Algorithm for a Class of Nonmonotonic Linear Complementary Problems

作　　者：张莉[1] 王浚岭[1] 张明望[1] 

机构地区：[1]三峡大学理学院数学系,湖北宜昌443002

出　　处：《工程数学学报》2007年第4期707-711,共5页Chinese Journal of Engineering Mathematics

基　　金：湖北省教育厅重点科研项目(D200613009)

摘　　要：通过对非单调线性互补问题所提出的一种内点算法进行分析,指出了算法中存在的关键性错误,在此基础上给出了求解一类非单调线性互补问题的宽邻域路径跟踪算法,给出了作为复杂性分析基础的两个重要关系式的正确表达式,并克服了由此带来的在收敛性分析中的一系列困难,成功地将线性规划问题的宽邻域内点算法,推广到非单调线性互补问题,讨论了算法的迭代复杂性。特别对于单调线性互补问题,得到了目前宽邻域内点算法迭代复杂性的最好结果。In the paper, an interior-point algorithm for nonmonotonic linear complementary problems is analyzed in detail, and the existing wrong results about the algorithm are pointed out. A wide-neighborhood path-following algorithm is presented by basing on the interior-point algorithm. Two correct expressions of complexity analysis foundation are given, and a series of difficulties are overcome during the convergence analysis. The wide-neighborhood path-following algorithm for linear programming is extended to nonmonotonic linear complementary problems successfully. Its iteration complexity is discussed. Specially, regarding the monotonous linear complementary problems, the best result of iteration complexity is obtained by wide-neighborhood interior-point algorithm.

关 键 词：非单调线性互补问题 P-矩阵 宽邻域路径跟踪法 计算复杂性 

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