摘要
将一种改进的满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.
出处
《西南师范大学学报(自然科学版)》
CAS
CSCD
北大核心
2012年第5期16-23,共8页
Journal of Southwest China Normal University(Natural Science Edition)
基金
湖北省自然科学基金项目(2008CDZ047)
关键词
单调线性互补问题
不可行内点算法
满Newton步
多项式复杂性
monotone linear complementarity problem infeasible interior-point methods full-Newton step polynomial complexity