Interior point algorithms for linear complementarity problems based on large neighborhoods of the central path

Gongyun ZHAO

In this paper we study a first-order and a high-order algorithm for solving linear complementarity problems. These algorithms are implicitly associated with a large neighborhood whose size may depend on the dimension of the problems. The complexity of these algorithms depends on the size of the neighborhood. For the first order algorithm, we a chieve the complexity bound which the typical large-step algorithms possess. It is well-known that the complexity of large-step algorithms is greater than that of short-step ones. By using high-order power series (hence the name high-order algorithm), the iteration complexity can be reduced. We show that the complexity upper bound for our high-order algorithms is equal to that for short-step algorithms.

Research Report No. 650, Dept of Mathematics, National University of Singapore, Singapore.