Complexity of large-update interior point algorithm for linear complementarity problems

✍ Scribed by G.M. Cho; M.K. Kim; Y.H. Lee

• Publisher: Elsevier Science
• Year: 2007
• Tongue: English
• Weight: 274 KB
• Volume: 53
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/j.camwa.2006.12.004

✦ Synopsis

In this paper we propose a new large-update primal-dual interior point algorithm for P * (κ) linear complementarity problems (LCPs). We extend Bai et al.'s primal-dual interior point algorithm for linear optimization (LO) problems to P * (κ) LCPs with generalized kernel functions. New search directions and proximity functions are proposed based on a simple kernel function which is neither a logarithmic barrier nor a self-regular. We show that if a strictly feasible starting point is available, then the new largeupdate primal-dual interior point algorithms for solving P * (κ) LCPs have O((1 + 2κ)n log nµ 0 ε ) polynomial complexity which is similar to the polynomial complexity obtained for LO and give a simple complexity analysis. This proximity function has not been used in the complexity analysis of interior point method (IPM) for P * (κ) LCPs before.