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

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

作　　者：朱丹花[1] 张明望[1] 

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

出　　处：《西南师范大学学报（自然科学版）》2012年第5期16-23,共8页Journal of Southwest China Normal University(Natural Science Edition)

基　　金：湖北省自然科学基金项目(2008CDZ047)

摘　　要：将一种改进的满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.

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

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