Polynomial Affine-Scaling Algorithms for $P_*(\kappa)$ Linear Complementarity Problems

T. Illes, C. Roos and T. Terlaky

A family of primal-dual affine-scaling algorithms is presented for Linear Complem entarity Problems (LCP's) with $P_*$-matrices. These algorithms were first introd uced by Jansen et al. for solving linear optimization problems and later also applied to LCP's with semidefinite matrices. We show that the same algorithmic concept applies to LCP's with $P_*$-matrices and that the resulting algorithms admit polynomial-time iteration bounds.

Key words: linear complementarity problems, $P_(*)$-matrices, affine-scaling algorithms

Reports of the Faculty of Technical Mathematics and Informatics Nr. 97-21, Delft University of Technology, Delft, March, 1997

Contact: [email protected]