High-order large-step interior point algorithms for linear complementarity problems

Zhao Gong Yun

In this paper we study a type of high-order large-step interior point algorithms 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. By using high-order power series (so the name high-order algorithm), the complexity can be reduced. We will show that the complexity upper bound for high-order large-step algorithms is asymptotically, as the order tends to infinity, equal to that for short-step algorithms.

Technical Report No. 650, Department of Mathematics, National University of Singapore, 0511, SINGAPORE

[DVI] [IP PAGE] [SEARCH AGAIN]