An interior point approach for linear complementarity problem using new parametrized kernel function

Abstract

In this paper, we propose a primal–dual interior point method for Linear Complementarity Problem (LCP) based on a new parameterized kernel function. The investigation according to it yields the best-known iteration bound $O(\sqrt{n}\log (n)\log (\frac{n}{ϵ}\left)\right)$ for large-update algorithm and thus improves the iteration bound obtained in Bai et al. (SIAM J Optim. 2004;15:101–128) for large-update algorithm. Finally, we present few numerical results to demonstrate the efficiency of the proposed algorithm.

Keywords:

• Linear optimization
• kernel function
• interior-point methods
• complexity bound

Acknowledgments

The authors would like to express their most sincere thanks and grateful acknowledgements to Professor Christiane Tammer, Editor-in-Chief for his considerable encouragement and to an anonymous referee for his valuable remarks and pertinent suggestions which were remarkably helpful in improving the content of the manuscript.

Disclosure statement

No potential conflict of interest was reported by the author(s).