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

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

对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||/ε).