Peng, Jiming; Roos, Cornelis; Terlaky, Tamás New complexity analysis of primal-dual Newton methods for \(P_* (\kappa)\) linear complementarity problems. (English) Zbl 0972.90081 Frenk, Hans (ed.) et al., High performance optimization. Dordrecht: Kluwer Academic Publishers. Appl. Optim. 33, 245-265 (2000). Summary: In this paper, we consider a primal-dual Newton method for linear complementarity problems (LCP) with \(P_*(\kappa)\)-matrix. By using some new analysis tools, we prove polynomial complexity of the large update method without using a barrier or potential function. Our analysis is based on an appropriate proximity measure only. This proximity measure has not been used in the analysis of a large update method for LCP before. Our new analysis provides a unified way to analyze both large update and small update methods. The polynomial complexity of the method of finding a maximally complementarity solution is discussed as well.For the entire collection see [Zbl 0933.00020]. Cited in 1 Document MSC: 90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) 90C51 Interior-point methods 68Q25 Analysis of algorithms and problem complexity 58E35 Variational inequalities (global problems) in infinite-dimensional spaces Keywords:linear complementarity problem; interior point method; primal-dual method; polynomial complexity; affine variational inequalities PDFBibTeX XMLCite \textit{J. Peng} et al., Appl. Optim. 33, 245--265 (2000; Zbl 0972.90081)