Bulletin of the
Korean Mathematical Society BKMS

In this paper we present new large-update primal-dual interior point algorithms for $P_* $ linear complementarity problems(LAPS) based on a class of kernel functions, $ \psi(t)= \frac{t^{p+1}-1}{p+1}+\frac1{\sigma}(e^{\sigma(1-t)}-1)$, $p\in[0,1],~\sigma\ge 1$. It is the first to use this class of kernel functions in the complexity analysis of interior point method(IPM) for $P_* $ LAPS. We showed that if a strictly feasible starting point is available, then new large-update primal-dual interior point algorithms for $P_* $ LAPS have $O((1+2\kappa)n^{\frac1{p+1}}\log{n} \log\frac{n}{\varepsilon})$ complexity bound. When $p=1$, we have $ O((1+2\kappa)\sqrt{n}\log {n}\log\frac{n}{\varepsilon})$ complexity which is so far the best known complexity for large-update methods.

Keywords: primal-dual interior point method, kernel function, complexity, polynomial algorithm, large-update, linear complementarity, path-following

MSC numbers: 90C33, 90C51