Family of Polynomial Affine Scaling Algorithms for Positive Semi-Definite LinearComplementarity Problems

摘要

In the paper the new polynomial affine scaling algorithm of Jansen, Roos andTerlaky for LP is extended to PSD linear complementarity problems. The algorithm is immediately further generalized to allow higher order scaling. These algorithms are also new for the LP case. The analysis is based on Ling's proof for the LP case, hence allows an arbitrary interior feasible pair to start with. Finally, the authors show that Monteiro, Adler and Resende's polynomial complexity result for the classical primal-dual affine scaling algorithm can easily be derived from their analysis. In addition, the result is valid for arbitrary not necessarily centered, initial points.