Bull. Korean Math. Soc. 2009; 46(3): 521-534
Printed May 1, 2009
https://doi.org/10.4134/BKMS.2009.46.3.521
Copyright © The Korean Mathematical Society.
Gyeong-Mi Cho and Min-Kyung Kim
Dongseo University and Pusan National University
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
© 2022. The Korean Mathematical Society. Powered by INFOrang Co., Ltd