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

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

对单调线性互补问题设计了一种新的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.