P_*(κ)线性互补问题的满Newton步不可行内点算法  

A New Full-Newton Infeasible Interior-point Algorithm for P_*(κ) Linear Complementarity Problem

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

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

出　　处：《数学物理学报（A辑）》2013年第4期746-758,共13页Acta Mathematica Scientia

基　　金：湖北省自然科学基金(2008CDZ047);湖北省教育厅自然科学研究项目(Q20111208)资助

摘　　要：对P_*(k)线性互补问题(LCP)提出了一种新的不可行内点算法,新算法是Mansouri等人最近对单调LCP提出的满Newton步不可行内点算法的改进和推广.通过在收敛分析中建立一些新的技术性结果,克服了P_*(k)LCP的非单调性给收敛分析带来的困难,证明了新算法的迭代复杂性为O((1+4k)_2nlog(max{(x^O)~Ts^o,‖r^O‖})/ε).This paper presents a new infeasible interior-point algorithm for P_*(κ) linear complementarity problems(LCP),which is an extension and improvement of a full-Newton step infeasible interior-point algorithm for monotone LCP proposed by Hansouri et al recently.With the non-monotone of the P_*(κ) LCP,we introduce some new technical results and prove that the algorithm has iteration complexity with O((1+4κ)~2n log(max{(x^0)}T_s^0,||r^0||/ε).

关 键 词：P*(k)线性互补问题 不可行内点算法 满Newton步 多项式复杂性 

分 类 号：O211.2[理学—概率论与数理统计]