×

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].

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
PDFBibTeX XMLCite