Abstract:

 A full-newton step infeasible interior-point algorithm for monotone linear complementarity problems based on a kernel function was presented. The main iteration of the algorithm consists of a feasibility step and several centrality steps. By using some new analysis tools, the polynomial complexity bound for the algorithm was obtained, namely, Onlogmax｛(x0)Ts0,‖r0‖｝n, which is consistent with the currently best iteration bound for infeasible interior-point methods of monotone linear complementarity.

Key words: linear complementarity problem; infeasible interior point algorithm; full-newton step; kernel function; polynomial complexity