Computational Optimization & Applications. 17(2-3):183–201, DECEMBER 2000

Issn Print: 0926-6003

Publication Date: December 2000

# A Complexity Analysis of a Smoothing Method Using CHKS-functions for Monotone Linear Complementarity Problems

Keisuke Hotta;Masatora Inaba;Akiko Yoshise;

+ Author Information

Institute of Policy and Planning Sciences, University of Tsukuba, Tsukuba, Ibaraki 305, Japan

### Abstract

We consider the standard linear complementarity problem (LCP): Find x,y, ∈ R2nsuch that y = Mx + q, (x,y, ≥ 0 and xiyi= 0 (i= 1, 2, …, n), where M is an n× n matrix and q is an n-dimensional vector. Recently several smoothing methods have been developed for solving monotone and/or P0LCPs. 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 a feasible interior point. After a smoothing method is provided, some properties of the CHKS-function are described. As a consequence, we show that the algorithm terminates in O (\frac{\bar{\gamma}^{6}n}{\epsilon^6} \hbox{ log }\frac{\bar{\gamma}^2n}{\epsilon^2}) Newton iterations where \bar{\gamma} is a number which depends on the problem and the initial point. We also discuss some relationships between the interior point methods and the smoothing methods.