A continuation method for linear complementarity problems with P₀ matrix

Abstract

In this article, we propose a new continuation method for solving the linear complementarity problem (LCP). The method solves one system of linear equations and carries out only a one-line search at each iteration. The continuation method is based on a modified smoothing function. The existence and continuity of a smooth path for solving the LCP with a P ₀ matrix are discussed. We investigate the boundedness of the iteration sequence generated by our continuation method under the assumption that the solution set of the LCP is nonempty and bounded. It is shown to converge to an LCP solution globally linearly and locally superlinearly without the assumption of strict complementarity at the solution under suitable assumption. In addition, some numerical results are also reported in this article.

Keywords:

• linear complementarity problems
• continuation methods
• global and superlinear convergence

Acknowledgements

This project is supported by the National Natural Science Foundation of China (Grant No. 11071041) and Fujian Natural Science Foundation (Grant No. 2009J01002).