A complexity analysis of a smoothing method using CHKS-functions for monotone li near complementarity problems

Keisuke Hotta, Masatora Inaba and Akiko Yoshise

We consider the standard monotone linear complementarity problem. Recently several smoothing methods have been developed for solving monotone and/or $P_0$ LCPs. The aim of this paper is to derive a complexity bound of smoothing methods using Chen-Harker-Kanzow-Smale functions in the case where the monotone LCP has an feasible interior point. After a smoothing method is provided, some properties of the CHKS-function are described. We also discuss some relationships between the interior point methods and the smoothing methods.

Discussion Paper Series No. 807, Institute of Policy and Planning Sciences, Univ ersity of Tsukuba, Tsukuba, Ibaraki 305, Japan.

Contact: yoshise@shako.sk.tsukuba.ac.jp