POLYNOMIALITY OF A HIGH-ORDER FEASIBLE INTERIORPOINT METHOD FOR SOLVING THE HORIZONTAL LINEAR COMPLEMENTARITY PROBLEMS
一个求解水平线性互补问题的高阶可行内点算法的多项式复杂性

Recently, Zhao and Sun presented a high-order infeasible interior point method (IPM) for solving the sufficient linear complementarity problem (LCP) which possesses highorder convergent rate when the LCP has no strictly complementary solution. But no polynomiality result was reported in their paper. In this paper, we consider a simple version of their algorithm, i.e., a high-order feasible IPM for solving the monotone horizontal linear complementarity problem. We prove that the iteration complexity of the method is of O().