New primal-dual interior point methods for {$ P_{*}(\kappa)$} linear complementarity problems
Commun. Korean Math. Soc. 2010 Vol. 25, No. 4, 655-669
https://doi.org/10.4134/CKMS.2010.25.4.655
Printed December 1, 2010
Gyeong-Mi Cho and Min-Kyung Kim
Dongseo University, Pusan National University
Abstract : In this paper we propose new primal-dual interior point methods (IPMs) for $P_*(\kappa) $ linear complementarity problems (LCPs) and analyze the iteration complexity of the algorithm. New search directions and proximity measures are defined based on a class of kernel functions, $ \psi(t)= \frac{t^2-1}{2}-\int^t_1 e^{q\left(\frac1{\xi}-1\right)}d\xi$, $q\ge1$. If a strictly feasible starting point is available and the parameter $q=\log \left(1+a\sqrt{\frac{2\tau+2\sqrt{2n\tau}+{\theta}n}{1-\theta}}\right),$ where $ a=1+\frac1{\sqrt{1+2\kappa}}$, then new large-update primal-dual interior point algorithms have $O((1+2\kappa)\sqrt{n}\log n\log\frac{n}{\varepsilon})$ iteration complexity which is the best known result for this method. For small-update methods, we have $ O((1+2\kappa)q\sqrt{qn}\log\frac{n}{\varepsilon})$ iteration complexity.
Keywords : primal-dual interior point method, kernel function, complexity, polynomial algorithm, large-update, linear complementarity problem
MSC numbers : 90C33, 90C51
Downloads: Full-text PDF  


Copyright © Korean Mathematical Society.
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