一种单调线性互补问题的full-Newton步不可行内点算法  

A New Full-Newton Step Infeasible Interior-Point Algorithm for Monotone Linear Complementarity Problem

作　　者：吴珊[1] 张明望[1] 黄正伟[2] 

机构地区：[1]三峡大学理学院,湖北宜昌443002 [2]三峡大学经济与管理学院,湖北宜昌443002

出　　处：《西南大学学报（自然科学版）》2016年第5期106-113,共8页Journal of Southwest University(Natural Science Edition)

基　　金：国家自然科学基金项目(71471102);宜昌市科学技术研究与开发项目(A2012-302-25)

摘　　要：对单调线性互补问题设计了一种新的full-Newton步不可行内点算法.该算法是对Liu Z和Sun W提出的线性规划的full-Newton步不可行内点算法的改进和推广.通过应用新的技术引理,证明了算法的多项式复杂性阶为O(nL),这与当前单调线性互补问题的不可行内点算法最好的迭代复杂性阶一致.In this paper, a full-Newton step infeasible interior-point algorithm is proposed for solving the monotone linear complementarity problem. The algorithm is an improvement and generalization of the full- Newton step infeasible interior-point algorithm for linear optimization proposed by Liu and Sun （Numer Algor 46：173--188, 2007）. By using some technical lemmas, the polynomial iteration complexity is ob- tained, namely, O（nL）, which coincides with the currently best known iteration bound for infeasible inte- rior-point methods for the monotone linear complementarity problem.

关 键 词：线性互补问题 full-Newton步 不可行内点算法 多项式复杂性 

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