Complexity of large-update interior point algorithm for P-*(kappa) linear complementarity problems
In this paper we propose a new large-update primal-dual interior point algorithm for P-*(K) linear complementarity problems (LCPs). We extend Bai et al.'s primal-dual interior point algorithm for linear optimization (LO) problems to P-*(K) LCPs with generalized kernel functions. New search directions and proximity functions are proposed based on a simple kernel function which is neither a logarithmic barrier nor a self-regular. We show that if a strictly feasible starting point is available, then the new large-update primal-dual interior point algorithms for solving P-* (kappa) LCPs have O ((1 + 2 kappa)n log n mu(0)/epsilon) polynomial complexity which is similar to the polynomial complexity obtained for LO and give a simple complexity analysis. This proximity function has not been used in the complexity analysis of interior point method (IPM) for P-* (K) LCPs before. (c) 2007 Elsevier Ltd. All rights reserved.
complexity large-update linear complementarity problem kernel function primal-dual interior point method polynomial algorithm