##
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.

Contact: matzgy@leonis.nus.sg