Communications of the
Korean Mathematical Society
CKMS

ISSN(Print) 1225-1763 ISSN(Online) 2234-3024

Article

HOME ALL ARTICLES View

Commun. Korean Math. Soc. 2010; 25(4): 655-669

Printed December 1, 2010

https://doi.org/10.4134/CKMS.2010.25.4.655

Copyright © The Korean Mathematical Society.

New primal-dual interior point methods for {$ P_{*}(\kappa)$} linear complementarity problems

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

Stats or Metrics

Share this article on :