一种新的求解单调线性互补问题的满Newton步不可行内点算法

On a New Full-Newton Step Infeasible Interior-Point Method for Monotone Linear Complementarity Problem

将一种改进的满Newton步不可行内点算法拓展到单调线性互补问题(LCP)中.由于单调LCP的迭代方向不再具有正交性,因此算法的收敛分析不同于线性规划的情况.通过提出一些新的分析工具,证明了算法具有迭代复杂性O(n log (max{(x0)Ts0,‖r0‖}/ε)).

In this paper the full-Newton step infeasible interior-point method for Linear Optimization （LO） introduced by Roos et. al. is extended to linear complementarity problem （LCP）. Since the orthogonality of the search directions of LCP may not be assumed, the analysis is different from that of LO. By using some new a-nalysis tools, we obtain the iteration bound of our method, namely for Owhichcoincides with the best known one for LCP.