caa a22 4500 475750578 CHVBK 20180406123522.0 cr unu---uuuuu 170329e20001201xx s 000 0 eng 10.1023/A:1026550331760 doi (NATIONALLICENCE)springer-10.1023/A:1026550331760 A Complexity Analysis of a Smoothing Method Using CHKS-functions for Monotone Linear Complementarity Problems [Elektronische Daten] [Keisuke Hotta, Masatora Inaba, Akiko Yoshise] We consider the standard linear complementarity problem (LCP): Find (x, y) ∈ R 2n such that y = M x + q, (x, y) ≥ 0 and x i y i = 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 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 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\left( {\frac{{\gamma ^{ - 6} n}}{{\varepsilon ^6 }}\log \frac{{\gamma ^{ - 2} n}}{{\varepsilon ^2 }}} \right)$$ 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. Kluwer Academic Publishers, 2000 smoothing method nationallicence complexity bound nationallicence linear complementarity problem nationallicence monotonicity nationallicence Hotta Keisuke Institute of Policy and Planning Sciences, University of Tsukuba, Ibaraki 305, Tsukuba, Japan aut Inaba Masatora Institute of Policy and Planning Sciences, University of Tsukuba, Ibaraki 305, Tsukuba, Japan aut Yoshise Akiko Institute of Policy and Planning Sciences, University of Tsukuba, Ibaraki 305, Tsukuba, Japan aut Computational Optimization and Applications Kluwer Academic Publishers 17/2-3(2000-12-01), 183-201 0926-6003 17:2-3<183 2000 17 10589 https://doi.org/10.1023/A:1026550331760 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1023/A:1026550331760 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Hotta Keisuke Institute of Policy and Planning Sciences, University of Tsukuba, Ibaraki 305, Tsukuba, Japan aut NATIONALLICENCE 700 1- Inaba Masatora Institute of Policy and Planning Sciences, University of Tsukuba, Ibaraki 305, Tsukuba, Japan aut NATIONALLICENCE 700 1- Yoshise Akiko Institute of Policy and Planning Sciences, University of Tsukuba, Ibaraki 305, Tsukuba, Japan aut NATIONALLICENCE 773 0- Computational Optimization and Applications Kluwer Academic Publishers 17/2-3(2000-12-01), 183-201 0926-6003 17:2-3<183 2000 17 10589 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer