一类新的求解P_*(κ)阵线性互补问题的多项式内点算法

A New Class of Polynomial Interior-Point Algorithm for P_*(κ) Linear Complementarity Problems

利用核函数及其性质，对P＊（K）阵线性互补问题提出了一种新的宽邻域不可行内点算法．对核函数作了一些适当的改进，所以是不同于Peng等人介绍的自正则障碍函数．最后证明了算法具有近似0（（1＋2k）n3/4；lognμo/ε）多项武复杂性，是优于传统的基于对数障碍函数求解宽邻域内点算法的复杂性．

In this paper, we propose a new large-update interior-point algorithm for P＊（k） linear complementarity problems based on kernel functions .We improve some mild conditions on the kernel functions and give a new class of kernel functions .so it is different from the selfregular, functions introduced by Peng. Finally, we show that the complexity of the algorithm 3 has so far worst case O（（1 ＋ 2k）n3/4 lognμo/ε）,which is better than the classical large-update algorithm based on the classical logarithmic barrier functions.