New complexity analysis of primal-dual IMPS for $P_{*}$ LAPS based on large updates
Bull. Korean Math. Soc. 2009 Vol. 46, No. 3, 521-534
https://doi.org/10.4134/BKMS.2009.46.3.521
Printed May 1, 2009
Gyeong-Mi Cho and Min-Kyung Kim
Dongseo University and Pusan National University
Abstract : 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
Downloads: Full-text PDF  


Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd